本文共 3240 字，大约阅读时间需要 10 分钟。
Wormholes
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)
Total Submission(s) : 81 Accepted Submission(s) : 27
While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N,M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.
As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .
To help FJ find out whether this is possible or not, he will supply you with complete maps toF (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.
23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8
NOYES
题意：
农民约翰在农场散步的时候发现农场有大量的虫洞，这些虫洞是非常特别的因为它们都是单向通道，为了方便现在把约翰的农田划分成N快区域，M条道路，W的虫洞。
#include#include #include #include #define inf 0x3f3f3f3fusing namespace std;struct paths{int s,e,t;}p[5210]; bool flag;int n,m,w,cnt;int dis[520];int main(){ int i,j,k,temp; int t; cin>>t; while(t--) { cin>>n>>m>>w; for(i=1;i<=m;i++){ cin>>p[i].s>>p[i].e>>p[i].t; p[i+m].s=p[i].e;p[i+m].e=p[i].s;p[i+m].t=p[i].t; //输入每点情况 } k=2*m+w; //注意这是边数。 for(i=2*m+1;i<=k;i++) { cin>>p[i].s>>p[i].e>>temp; p[i].t=-temp; } m=k; for(j=1;j<=n;j++) dis[j]=inf;//初始化 dis[1]=0; for(j=1;j<=n;j++) { flag=0; for(k=1;k<=m;k++) { if(dis[p[k].s]>p[k].t+dis[p[k].e]){ dis[p[k].s]=p[k].t+dis[p[k].e];flag=1; } } if(!flag)break; //优化 } flag=0; for(k=1; k<=m; k++) //如果仍有大于它的则出现负环 { if(dis[p[k].s]>p[k].t+dis[p[k].e]){flag=1;break;} } if(flag)cout<<"YES"<
转载地址：https://blog.csdn.net/sinat_37668729/article/details/76977921 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
