SPATHS - Shortest Paths

no tags 

Nikola lives in Bittown and he is in love with his girlfriend Anita from a town called Hextown. Nikola knows the country map very well, and he found the shortest path between these two towns. He calls this path lucky path. The map of the country can be described as a collection of towns connected with bidirectional roads.

One day the president of this country decided that there are going to be some works on the roads. In order to uphold the traffic in the country, only one road is going to be closed per day.

For each road on the lucky path, Nikola wants to know the length of the shortest path between Anita and him if that road is closed.

Input

The first line of input contains four integers: n - the number of cities, m - the number of roads between these towns, a - index of town Bittown where Nikola lives, b - the index of town Hextown where Anita lives. Towns are indexed with numbers 1, 2 ... n. Next m lines specify roads: each line contains three integers: u, v and w - there exist road between towns u and v with length w.

Last line of the input contains number k followed by k numbers a = v1, v2 ... vk = b - the lucky path that Nikola uses. 

Output

For every integer t = 1 ... k - 1, in separate line, print the length of the shortest path between cities a and b, if the road (vt, vt + 1) is closed. If there is no such path, output “-1” without quotes. 

Example

Input:
5 6 1 5
1 2 1
2 3 3
2 5 100
3 4 3
3 5 5
4 5 3
4 1 2 3 5

Output:
-1
101
10

Constraints

  • -1 ≤ n ≤ 2000, 1 ≤ m ≤ 100,000
  • 1 ≤ a, b ≤ n
  • 1 ≤ w ≤ 100,000
  • There is at most one road between each pair of cities.
  • You may assume that the given path is one of the shortest paths that connects given two cities a and b.

hide comments
robertdevries: 2015-12-03 20:47:34

I joined SPOJ last week and am trying to solve this problem. After submitting and successful compilation I see Running(1), Running(2).......Running(10) displayed followed by 'Wrong answer'.
What does all that Running(nr) mean? Is the program run multiple times successfully with different inputs and only gives a wrong answer on the 10th run?

Re (Kata) : When you submit a solution, it will run for all testcases, Running(n) means it's running on n-th testcases. But even if it gives WA, TLE,... for some testcases, the program still run to the last testcases, and if your solution doesn't pass all testcases, the result will be the first testcase 's bad result (WA, TLE, RE,...)

Last edit: 2015-12-07 17:23:51
Noman Ahmed Sheikh: 2015-08-15 23:48:24

@Kata
Can you tell me if my solution runtime is anywhere close to the required running time?

[Kata] : No. Your solution is too slow to got Accpept

Last edit: 2015-08-18 16:00:44
LeppyR64: 2015-01-16 13:01:07

Thanks for the update! Back to the drawing board.

Kata: 2015-01-16 06:12:24

There are 3 Accepted submissions. Two of them was disqualified. Maybe the user of the last one checked "Remove me from the user ranking", so it wasn't display on rank list.

Edit : Time limit was a little strict. I have increased it to 1s

@LeppyR64 : I have rejudged your 3 last submissions. None of them could pass in 1s (or even 3s)

Last edit: 2015-01-16 06:27:31
LeppyR64: 2015-01-15 18:10:18

Is your timelimit too strict? I have submitted a solution that I believe should be acceptable. O(k(n+m)) I only ask because it has been over a month with no successful submissions. I will open a topic on the forum in the Problemset bugs section.

Last edit: 2015-01-15 18:10:38
simararorarox9: 2014-12-17 05:25:15

bound on k ?
"You may assume that the given path is one of the shortest paths that connects given two
cities a and b."

Last edit: 2014-12-22 13:46:54

Added by:Kata
Date:2014-12-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:BOI