TRVCOST - Travelling cost
The government of Spoj_land has selected a number of locations in the city for road construction and numbered those locations as 0, 1, 2, 3, ... 500.
Now, they want to construct roads between various pairs of location (say A and B) and have fixed the cost for travelling between those pair of locations from either end as W unit.
Now, Rohit being a curious boy wants to find the minimum cost for travelling from location U (source) to Q number of other locations (destination).
Input
First line contains N ,the number of roads that government constructed.
Next N line contains three integers A ,B, and W.
A and B represent the locations between which the road was constructed and W is the fixed cost for travelling from A to B or from B to A.
Next line contains an integer U from where Rohit wants to travel to other locations.
Next line contain Q, the number of queries (finding cost) that he wants to perform.
Next Q lines contain an integer V (destination) for which minimum cost is to be found from U.
Output
Print the required answer in each line.
If he can't travel from location U to V by any means then, print 'NO PATH' without quotes.
Example
Input: 7 0 1 4 0 3 8 1 4 1 1 2 2 4 2 3 2 5 3 3 4 2 0 4 1 4 5 7 Output: 4 5 9 NO PATH
Constraints
1 <= N <= 500
0 <= A, B <= 500
1 <= W <= 100
0 <= U, V <= 500
1 <= Q <= 500
Explanation
Query #1: 0 → 1: cost = 4
Query #2: 0 → 4: 0 → 1 → 4, cost = 4 + 1 = 5
Query #3: 0 → 5: 0 → 1 → 2 → 5, cost = 4 + 2 + 3 = 9
Query #4: 0 → 7: no path exist between 0 and 7
hide comments
Prateek Sharma:
2015-03-19 19:17:06
can you give some hint why I am getting WA.
|
|
LeppyR64:
2015-03-11 13:59:24
The formatting for the problem statement is not good with the new design. Don't manually add linebreaks in the middle of sentences.
|
|
[Lakshman]:
2015-03-10 17:21:31
@ivar.raknahs can you give some hint why I am getting WA.
|
|
RIVU DAS:
2015-03-06 19:33:36
Can you please recheck your input files? I think there's a mistake in them.
|
|
priyank:
2015-03-06 13:37:03
running perfectly upto 9 test case while in 10 it gives NZEC error why??
|
Added by: | ivar.raknahs |
Date: | 2015-03-05 |
Time limit: | 0.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 JS-MONKEY |
Resource: | own |