Shortest Path

AC一覧

Problem Statement
問題文

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.

$N$ 頂点 $M$ 辺の単純重み付き有向グラフが与えられます。$i$番目の辺は頂点 $a_i$ から頂点 $b_i$ に張られており、重さは $c_i$ です。

頂点 $s$ から 頂点 $t$ への(単純な)最短パスを一つ構築してください。パスが存在しない場合その旨を報告してください。

Constraints
制約

Input
入力

$N$ $M$ $s$ $t$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
$\vdots$
$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.

頂点 $s$ から頂点 $t$ へのパスが存在しない場合-1を出力してください。 そうでない場合以下の形式で出力してください。

$X$ $Y$
$u_0$ $v_0$
$u_1$ $v_1$
$u_2$ $v_2$
$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_i, v_i$はそれぞれ$i$番目に通る辺の始点と終点を表します。 同じ頂点を $2$ 回以上通ってはなりません。

Sample
サンプル

# 1

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
11 3
2 1
1 0
0 3

# 2

2 1 0 1
1 0 10
-1

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions