Wormholes.(POJ-3259)
发布时间：2020-12-13 20:46:27 所属栏目：PHP教程 来源：网络整理
导读：最短路Bellman的算法，只需用到判断是不是存在负圈的部份，由于只要存在负圈，则1定有1条路可以返回出发点并且时间还原（1开始题意理解的不好，注意如果返回出发点的时间为负数，其实也是可以的，应当是默许了返回起始时间，由于时间不能为负。） 所以，实质
|
最短路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,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",&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;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |