Wormholes
InterviewTime limit2sMemory limit128 MB
Given roads with positive weights and wormholes with negative weights, detect whether any negative cycle exists in the resulting directed graph using Bellman-Ford.
- Level
Medium4 of 10
- Topics
- Shortest path, Graph, Dynamic programming
- Solved
- No attempts yet
Problem
A country has N locations, M bidirectional roads, and W one-way wormholes. Traveling along a road takes the given amount of time. Traveling through a wormhole moves from its start location to its end location, but the arrival time is earlier than the departure time by the given amount.
Determine whether it is possible to start from some location, travel through roads and wormholes, return to the same location, and have the time be earlier than when the trip began.
Input
The first line contains the number of test cases TC (1 <= TC <= 5).
Each test case begins with three integers N, M, and W: the number of locations, roads, and wormholes (1 <= N <= 500, 1 <= M <= 2500, 1 <= W <= 200).
The next M lines each contain three integers S, E, and T, describing a bidirectional road between locations S and E that takes T time to traverse.
The next W lines each contain three integers S, E, and T, describing a one-way wormhole from S to E that makes time decrease by T.
The value T is an integer from 0 to 10000. Multiple roads may connect the same pair of locations. Locations are numbered from 1 to N.
Output
For each test case, print YES if it is possible to return to the starting location with time decreased. Otherwise, print NO.