POJ - 2387 Til the Cows Come Home——dijkstra

POJ - 2387 Til the Cows Come Home——dijkstra

一开始WA，到网上看了看貌似是重边的问题，但题目中的重边不是最新的那一条而是最小的那一条，我的dijkstra无所畏惧，最后看了看原来是输入写反了、、、、、、

#include #include #include #include #include #include using namespace std;typedef pair P;const int INF = 0x3f3f3f3f;const int maxn = 2010;int n, m, u, v, cost, d[maxn], vis[maxn];vector

g[maxn];void dijkstra() { for (int i = 1; i <= n; i++) { d[i] = INF, vis[i] = 0; } d[1] = 0; priority_queue, greater

> q; q.push(make_pair(0, 1)); while(!q.empty()) { u = q-().second; q.pop(); if(vis[u]) continue; vis[u] = 1; for (int i = 0; i < g[u].size(); i++) { v = g[u][i].first, cost = g[u][i].second; if (d[v] > d[u] + cost) { d[v] = d[u] + cost; q.push(make_pair(d[v], v)); } } }}int main() { while (~scanf("%d %d", &m, &n)) { for (int i = 1; i <= n; i++) g[i].clear(); for (int i = 1; i <= m; i++) { scanf("%d %d %d", &u, &v, &cost); g[u].push_back(make_pair(v, cost)); g[v].push_back(make_pair(u, cost)); } dijkstra(); printf("%d\n", d[n]); } return 0;}

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