Wormholes Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 48460 Accepted: 17861 Description
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 to F (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.
Input
Line 1: A single integer, F. F farm descriptions follow. Line 1 of each farm: Three space-separated integers respectively: N, M, and W Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path. Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds. Output
Lines 1..F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes). Sample Input
2 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 3 2 1 1 2 3 2 3 4 3 1 8 Sample Output
NO YES Hint
For farm 1, FJ cannot travel back in time. For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this. 翻译： 虫洞 时间限制:2000msmemory极限: 65536k 呈件共计:48460accepted 描述
在探索他的许多农场,农民约翰发现了一些惊人的虫洞。一个虫洞是非常奇特的,因为它是一条在你进入虫洞之前的时间将你送到目的地的单向路径。FJ的每个农场包括n ( 1 )字段,方便编号为1 ..n、m ( 1 2500 )路径,和w ( 1 200 )虫洞。
由于FJ是一个狂热的时间旅行爱好者,他想做以下工作:在某个领域开始,通过一些路径和虫洞旅行,在他初次离开之前回到起点。也许他能见见自己:)。
为了帮助FJ找出这是否可能,他将给你提供完整的地图,f ( 1 )他的农场。没有路径需要超过10000秒的路程,没有虫洞可以使FJ及时返回10,000秒。
输入
第1行:一个单一的整数,f1场描述跟踪。 每个农场的第一行:三个空间分开的整数:n , m和w。 每个农场的2+ 1号线:分别描述的三个空间分开的数字( s , e , t ) : s和e之间的双向路径,需要t秒的遍历。两个字段可能由多个路径连接。 每个农场的m+ 2 ..m +维丁格尔:三个分别描述的空间-分隔的编号( s , e , t ) :从s到e的单向路径,也会移动旅行者返回t秒。 输出
第1行:对于每个农场,如果FJ可以实现他的目标,输出“是”,否则输出“no”(不包括报价)。 样本输入
2 . 3 3 1 2 1 41 2 1 3 1 3 2 1 2 2 41 3 1 样本输出
没有 是的 提示
对于1号农场,FJ不能及时返回。 对于农场2, FJ可以通过循环1 - > 2 - > 3 - > 1及时返回,在离开之前到达他的起始位置1秒。他可以从这个周期的任何地方开始这样做。 做法：从题意可知，就是判断负权回路，这里用的是bellman_ford算法 代码如下：
#include <iostream> using namespace std; int x[50000],y[50000],z[50000],d[6000],t,n,m,p,w; int main() { cin>>t; while (t>0) { cin>>n>>m>>w; p=0; t--; for (int i=1;i<=m;i++) { p++; cin>>x[p]>>y[p]>>z[p]; p++; y[p]=x[p-1]; x[p]=y[p-1]; z[p]=z[p-1]; } for (int i=1;i<=w;i++) { p++; cin>>x[p]>>y[p]>>z[p]; z[p]=0-z[p]; } bool f; for (int i=1;i<=5999;i++) d[i]=1000000; d[1]=0; for (int i=1;i<=n;i++) { f=false; for (int j=1;j<=p;j++) if(d[x[j]]+z[j]<d[y[j]]) { f=true; d[y[j]]=d[x[j]]+z[j]; } if (not f) break; } f=false; for (int i=1;i<=p;i++) if (d[x[i]]+z[i]<d[y[i]]) { cout<<"YES"<<endl; f=true; break; } if (not f) cout<<"NO"<<endl; } }