链接地址:http://poj.org/problem?id=3259
大意:
N (1 ≤ N ≤ 500) 总共N个点(编号1..N)
M (1 ≤ M ≤ 2500) M条双向边
W (1 ≤ W ≤ 200) wormholes. W条单向负权边 (不知道 “虫洞”是神马的童鞋 百度~)
问从某个点开始走,能否回到过去。能就输出“YES”,否则输出“NO”。
思路:
看成一张图,回到过去理解为是否会出现负权环,用Bellman-Ford算法即可找出负权环。
Accepted | 448K | 79MS | G++ | 1357B |
#include <stdio.h> #include <string.h> #define INF 0x7f7f7f7f struct node { int v, u, len; } edges[5205]; int d[505]; int N, M, W, e; int bellman() { int i, j, mark; memset(d,INF,sizeof(d)); for(i=1; i<N; i++) { mark = 1; for(j=0; j<e; j++) { node& t = edges[j]; if(d[t.v]>d[t.u] + t.len) { d[t.v] = d[t.u] + t.len; mark = 0; } } if(mark) break; } for(i=0; i<e; i++) if(d[edges[i].v] > d[edges[i].u]+edges[i].len) { return 1; } return 0; } int main() { int T, i, a, b, len; scanf("%d",&T); while(T--) { scanf("%d%d%d",&N,&M,&W); e = 0; for(i=0; i<M; i++) { scanf("%d%d%d",&a,&b,&len); edges[e].v = a; edges[e].u = b; edges[e].len = len; e++; edges[e].v = b; edges[e].u = a; edges[e].len = len; e++; } for(i=0; i<W; i++) { scanf("%d%d%d",&a,&b,&len); edges[e].v = a; edges[e].u = b; edges[e].len = -len; e++; } if(bellman()) printf("YES\n"); else printf("NO\n"); } }