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
23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8
Sample Output
NOYES
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.
题意:走一条路会花费时间 走虫洞会时间倒流 问能不能走回起点的时候时间倒流
思路:其实就是判断有没有环 有环的话
看题的时候看了半天不知道起点到底是哪一个点
感觉现在bellman写的还挺顺手的了
一个加边的addedge函数 一个判断松弛的relax函数
然后外面一个for循环遍历n-1次 里面的for循环松弛每一条边
再对每一条边判断能不能松弛 能就说明有环
有环其实就说明这个路径上有负的
不然干吗要不停的重复走???
只有可以不断减小才会形成环
WA了一发是因为加边的时候的cnt没有初始化
代码:
#include #include #include #include #include