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


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

hide comments
2020-07-24 09:59:37
@sanchit_aga I assumed N=501 and got AC.
2019-08-21 18:42:49
AC with dijkstra and floyd-warshall :)
2019-07-10 02:04:15
@suyashky the tc you provided is wrong...the answer for the last query will be 6 not 8
2019-06-30 22:27:50
Make sure to store min cost if any edge occurs more than once in I/P
This might help!
20
10 11 11
2 3 5
2 6 3
2 1 4
2 4 2
5 2 3
4 6 2
3 4 6
3 4 6
2 3 5
3 4 6
6 4 5
1 2 4
1 3 8
1 4 1
1 4 4
4 2 3
3 4 2
2 4 1
3 4 2
3
5
8
6
2
4
5

O/p:
NO PATH
4
3
2
8

Last edit: 2019-06-30 22:28:32
2019-06-25 14:20:48
With dijkstra AC
floyd warshall WA
2019-04-19 13:56:22
Can anyone check what is wrong with my code submission id:> 23657325
I have taken every case but still got WA .
Thanks in advance
2019-01-19 18:39:12
Simple Dijkstra. AC in one go :) .Just a few hints

*****SPOILER ALERT*****



1) Assume when the source and destination are same
2) Input can contain some edges more than once
2019-01-11 12:50:21
i got WA assuming 501 vertices, changed it to 502 and AC.
2018-12-25 20:30:45
What if the input contain same edges, should I ignore them or update cost?
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.