Wormholes.(POJ-3259)
來源：程序員人生 發布時間：2015-08-05 08:23:09 閱讀次數：3132次
最短路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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
