Wormholes.(POJ-3259)
来源：程序员人生 发布时间：2015-08-05 08:23:09 阅读次数：3007次
最短路Bellman的算法，只需用到判断是不是存在负圈的部份，由于只要存在负圈，则1定有1条路可以返回出发点并且时间还原（1开始题意理解的不好，注意如果返回出发点的时间为负数，其实也是可以的，应当是默许了返回起始时间，由于时间不能为负。） 所以，实质就是判断是不是存在负圈。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int INF = 10000000;
int F,n,m,w,d[2000],all_edge,a,b,c;
struct edge{
int from,to,cost;
edge(int from = 0,int to = 0,int cost = 0) : from(from),to(to),cost(cost) {}
}s[6000];
bool bellman() {
memset(d,0,sizeof(d));
for(int i=0;i<n;i++) {
for(int j=0;j<all_edge;j++) {
edge e = edge(s[j].from,s[j].to,s[j].cost);
if(d[e.to] > d[e.from] + e.cost) {
d[e.to] = d[e.from] + e.cost;
if(i==n⑴) return true;
}
}
}
return false;
}
int main() {
scanf("%d",&F) ;
while(F--) {
scanf("%d%d%d",&n,&m,&w);
all_edge = 0;
for(int i=1;i<=m;i++) {
scanf("%d%d%d",&a,&b,&c);
s[all_edge].from = a;
s[all_edge].to = b;
s[all_edge++].cost = c;
s[all_edge].from = b;
s[all_edge].to = a;
s[all_edge++].cost = c;
}
for(int i=1;i<=w;i++) {
scanf("%d%d%d",&a,&b,&c);
s[all_edge].from = a;
s[all_edge].to = b;
s[all_edge++].cost = -c;
}
if(bellman()) printf("YES
");
else printf("NO
");
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
