TRVCOST - Travelling cost
The government of Spoj_land has selected 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
|
vineetjai:
2020-07-24 09:59:37
@sanchit_aga I assumed N=501 and got AC. |
|
vivek8420:
2019-08-21 18:42:49
AC with dijkstra and floyd-warshall :) |
|
subashsroy:
2019-07-10 02:04:15
@suyashky the tc you provided is wrong...the answer for the last query will be 6 not 8 |
|
suyashky:
2019-06-30 22:27:50
Make sure to store min cost if any edge occurs more than once in I/P
|
|
sanjana_17:
2019-06-25 14:20:48
With dijkstra AC
|
|
codercrush:
2019-04-19 13:56:22
Can anyone check what is wrong with my code submission id:> 23657325
|
|
aryan12:
2019-01-19 18:39:12
Simple Dijkstra. AC in one go :) .Just a few hints
|
|
sanchit_aga:
2019-01-11 12:50:21
i got WA assuming 501 vertices, changed it to 502 and AC. |
|
marethyu1:
2018-12-25 20:30:45
What if the input contain same edges, should I ignore them or update cost? |
|
imnnquy:
2018-12-20 16:21:44
For those who getting NZEC at TC10: Check all constrains and have your arrays size follow the constrains not N |
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 |