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
gautam: 2016-03-15 20:23:40

i am getting WA....can anyone help me,my sol id =16518098.???

raj_394: 2016-03-13 14:31:55

All those who wre getting NZEC... plz check the constraints... and take the size of arrays according to them.
NOte: size of arrays does not depend on N.
for those who are getting WA : there may be more than one path btw same pair.. adj matrix should contain min value.

try2catch: 2016-02-12 16:44:50

for those who getting wrong answers
1.check - whether graph is directed or in-directed
2.think - when to add the 'cost' of an edge and when to ignore it.
Its a good problem. don't search for more hints. Just implement Dijkstra correctly.
A good test case i think:
6
2 1 4
2 4 2
5 2 3
1 2 4
1 4 1
1 4 4
1
1
5
o/p=6

harshgupta007: 2016-02-08 15:30:28

Can we do this using Floyd Warshall. I used Floyd Warshall, but i am getting wrong answer.

Mateusz Kwasniak: 2015-09-07 18:16:50

PROTIP
Two-way roads (undirected graph)

harshit sharma: 2015-09-03 18:47:14

Easy one . Double century :)

:.Mohib.:: 2015-07-06 00:27:24

Good One... :)

Abhilash: 2015-04-16 21:11:42

AC in one

Last edit: 2015-04-16 21:12:46
joogle: 2015-03-22 16:08:46

I have checked every cases,but still getting WA.
Can anyone help me,my sol id = 13925292 ????

joogle: 2015-03-22 16:02:19

if both source and destination are same,then the output should be NO PATH or 0??
-reply-> print 0

Last edit: 2015-03-25 18:16:40

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