题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2544
最短路，学了写SPFA，判断负环很方便。
1 #include <cstdio> 2 #include <queue> 3 #include <vector> 4 #include <cstring> 5 #include <iostream> 6 #include <algorithm> 7 using namespace std; 8 typedef pair<int, int> pii; 9 10 const int maxn = 110; 11 const int maxm = 10100; 12 const int inf = 0x7f7f7f; 13 const int nl = 100; 14 vector<pii> G[maxn]; 15 int vcnt[maxn]; 16 int d[maxn]; 17 queue<int> q; 18 int n, m; 19 20 bool spfa(int s) { 21 for(int i = 1; i <= n; i++) d[i] = inf; 22 memset(vcnt, 0, sizeof(vcnt)); 23 d[s] = 0; q.push(s); 24 while(!q.empty()) { 25 int u = q.front(); q.pop(); 26 for(int i = 0; i < G[u].size(); i++) { 27 int v = G[u][i].first; 28 int w = G[u][i].second; 29 if(d[v] > d[u] + w) { 30 d[v] = d[u] + w; 31 vcnt[v]++; 32 q.push(v); 33 if(vcnt[v] > nl) return 0; 34 } 35 } 36 } 37 return 1; 38 } 39 40 int main() { 41 // freopen("in", "r", stdin); 42 int u, v, w; 43 while(~scanf("%d%d",&n,&m) && n + m) { 44 for(int i = 1; i <= n; i++) G[i].clear(); 45 for(int i = 0; i < m; i++) { 46 scanf("%d%d%d",&u,&v,&w); 47 G[u].push_back(pii(v, w)); 48 G[v].push_back(pii(u, w)); 49 } 50 spfa(1); 51 printf("%d ", d[n]); 52 } 53 return 0; 54 }