
 1.3K通过
 3.7K提交
 题目提供者 FarmerJohn2
 评测方式 云端评测
 标签 SPFA 深度优先搜索,DFS 背包 USACO 2006
 难度 普及+/提高
 时空限制 1000ms / 128MB
最新讨论 显示
题目描述
While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a oneway 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 timetraveling 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.
John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N （从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。 现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。
输入输出格式
输入格式：Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three spaceseparated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three spaceseparated 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 spaceseparated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.
输出格式：Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).
输入输出样例
说明
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.