Bombs On Roads
All submissions for this problem are available.
The evil Lex Luthor wants to separate Batman from Superman while he attacks Superman with his Kryptonie suit. But Batman, who is always 27 steps ahead of everyone, predicts that Luthor will blow up one of the bidirectional roads on the shortest path from Gotham to Metropolis. Each road is between 2 cities. Some cities may not have roads between them. To be able to help Superman in time, Batman will have to find out what will be the new shortest path if one of the roads on the original one will be blown up. There is a unique path from Gotham to Metropolis. Help Batman make his plan.
First line contains number of test cases
The first line contains 4 integers, the number of cities, n, and the number of roads, m, the city number of Gotham s, and
- m lines follow, with 3 integers, u, v and w, denoting a road of length w miles between the cities numbered u and v.
- Print k integers, the kth integer being the length of the shortest path from Gotham to Metropolis when the kth edge on the shortest
path is blown up.
- n <= 1e5
- Sum of n over all test cases <= 1e5+1000
- Sum of m over all test cases <= 2e5+1000
- w<= 1e9
- 1<= u,v,s,t <= n
Let the number of edges on the path from u to v be k.
Input: 1 5 5 1 5 1 2 1 2 3 1 3 4 1 4 5 1 1 4 9 Output: 10 10 10 -1
Example case 1 : The edge not in the path, of weight 9 units can be used for all the first 3 edges. Since the final edge is a bridge edge, deleting it disconnects 1 and 5.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions