TRVCOST - Travelling cost


 

The government of spojland 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 locations from either end  as W.
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).

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
shahi9935: 2018-06-16 16:50:28

Thanks @sherlock11. Your warning was of great help.

sherlock11: 2018-06-08 13:11:24

input contains same edges more than once..........so take care of that

ameyanator: 2018-03-30 18:54:01

It appears that the test cases are weak. My Floyd Warshall algo was giving the wrong answer but still it ran correctly. Also a huge running time gap between floyd warshall and dijkstra!

nadstratosfer: 2018-02-17 04:44:22

Constraints are stated correctly, got AC assuming U,V <= 500. Read older comments for WA-related hints. Good problem.

ztoa1: 2017-08-28 05:12:24

Those getting error in test case 10,check for :
when source is same as destination
output must be 0.

anubhav1772: 2017-07-24 19:03:40

AC in 1 GO :)

ankitshrey112: 2017-07-05 22:40:35

If you are getting wrong answer at test case 10 , then consider it is an undirected graph.

vaibhavk31: 2017-06-21 22:55:50

With djikstras AC
floyd warshall-WA

akshay_agarwal: 2017-06-10 20:59:28

getting wa on test 10 again and again , even made the array of size 1100. Please help.

Last edit: 2017-06-10 21:00:04
komninos: 2017-04-29 16:47:18

Last edit: 2017-04-29 16:48:18

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