8204: [yosupo] Graph - Shortest Path
[Creator : ]
Description
You are given a simple directed weighted graph, consisting of N vertices and M edges.
The i-th edge is directed from vertex $a_i$ to vertex $b_i$ and has a weight of $c_i$.
Find the (simple) shortest path from vertex s to vertex t, or report that no such path exists.
If there are multiple shortest paths, print any of them.
The i-th edge is directed from vertex $a_i$ to vertex $b_i$ and has a weight of $c_i$.
Find the (simple) shortest path from vertex s to vertex t, or report that no such path exists.
If there are multiple shortest paths, print any of them.
Input
$N\ M\ s\ t$
$a_0\ b_0\ c_0$
$a_1\ b_1\ c_1$
$⋮$
$a_{M−1}\ b_{M−1}\ c_{M−1}$
$a_0\ b_0\ c_0$
$a_1\ b_1\ c_1$
$⋮$
$a_{M−1}\ b_{M−1}\ c_{M−1}$
Output
If there are no paths from vertex s to vertex t, output -1. Otherwise, output one of the shortest paths in the following format.
$X\ Y$
$u_0\ v_0$
$u_1\ v_1$
$⋮$
$u_{Y−1}\ v_{Y−1}$
X represents length of the shortest path. Y represents the number of edges in the path. $u_i$ and $v_i$ are beginning and end of the i-th edge in the path, respectively.
$X\ Y$
$u_0\ v_0$
$u_1\ v_1$
$⋮$
$u_{Y−1}\ v_{Y−1}$
X represents length of the shortest path. Y represents the number of edges in the path. $u_i$ and $v_i$ are beginning and end of the i-th edge in the path, respectively.
Constraints
$2≤N≤500,000$
$1≤M≤500,000$
$0≤s<N$
$0≤t<N$
$s\neq t$
$0≤a_i<N,\ 0≤b_i<N,\ a_i\neq b_i$
$(a_i,b_i)\neq (a_j,b_j)\ (i\neq j)$
$0≤c_i≤10^9$
$1≤M≤500,000$
$0≤s<N$
$0≤t<N$
$s\neq t$
$0≤a_i<N,\ 0≤b_i<N,\ a_i\neq b_i$
$(a_i,b_i)\neq (a_j,b_j)\ (i\neq j)$
$0≤c_i≤10^9$
Sample 1 Input
5 7 2 3
0 3 5
0 4 3
2 4 2
4 3 10
4 0 7
2 1 5
1 0 1
Sample 1 Output
11 3
2 1
1 0
0 3
Sample 2 Input
2 1 0 1
1 0 10
Sample 2 Output
-1