Wormholes.(POJ-3259)

最短路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;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » Wormholes.(POJ-3259)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡