HDU 2544 最短路——dijlstra

HDU 2544 最短路——dijlstra

这题c++编译器有坑，用g++吧。

套用了dijkstra模板，没什么坑，WA的话检查一下初始化，以及模板是否写错

#include #include #include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 110;typedef pair P;struct Edge { int to, cost;};vector G[maxn];int n, m, d[maxn], vis[maxn];void dijkstra(int s) { priority_queue, greater

> q; memset(vis, 0, sizeof(vis)); for (int i = 0; i <= n; i++) d[i] = INF; d[s] = 0; q.push(P(0, s)); while (!q.empty()) { P p = q-(); q.pop(); int pos = p.second; if (vis[pos]) continue; vis[pos] = 1; int len = G[pos].size(); for (int i = 0; i < len; i++) { Edge e = G[pos][i]; if (d[e.to] > d[pos] + e.cost) { d[e.to] = d[pos] + e.cost; q.push(P(d[e.to], e.to)); } } }}void input() { for (int i = 0; i <= n; i++) G[i].clear(); int a, b, c; while (m--) { scanf("%d %d %d", &a, &b, &c); Edge e1, e2; e1.to = b, e1.cost = c; e2.to = a, e2.cost = c; G[a].push_back(e1); G[b].push_back(e2); }}int main(){ while (scanf("%d %d", &n, &m) == 2 && (n || m)) { input(); dijkstra(1); printf("%d\n", d[n]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。