問題一覧 > 通常問題

No.1364 [Renaming] Road to Cherry from Zelkova

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 60
作問者 : 👑 KazunKazun / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか) 37zigen37zigen
1 ProblemId : 5799 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-22 17:30:44

注意

yukicoder contest 279 (Zelkova and Cherry) の問題は 難易度順に並んではいない. よって, 問題文や難易度を表すの星の数, 正解者数等といった公開されている情報から問題を取捨選択することを強く推奨する.

問題文

$0$ から $N$ の番号がついた $N+1$ 個の頂点といくつかの有向辺からなる有向グラフがある. このグラフには $j=1, \dots, M $ に対して, 頂点 $u_j$ から 頂点 $v_j$ へ長さ $l_j$ で結ぶ有向辺が $a_j$ 本ある. なお, この有向グラフに自己ループは存在しない. このグラフにおいて, 頂点 $0$ から頂点 $N$ への歩道を全て考えたとき, 長さの総和が有限ならば, 総和を $10^9+7$ で割った余りを求め, 無限ならば, その旨を報告せよ. なお, 2つの歩道について, 辿った頂点の順番が同じでも, 用いた辺が同じでなければ, 異なる歩道とする.

訳注

有向辺 $e$ について, $s(e), t(e)$ でそれぞれ $e$ の始点, 終点を表すとする. このとき, 有向辺 $e$ に対して, $s(e)=t(e)$ であるとき, 辺 $e$ は自己ループであるという.

辺の列 $e_1, \dots, e_k$ が以下をみたすとき, $W=(e_1, \dots, e_k)$ は歩道であるという.

  • $i=1, \dots, k-1$ に対して, $t(e_i)=s(e_{i+1})$ を満たす.
特に, 歩道 $W=(e_1, \dots, e_k)$ に対して, $s(e_1)=0, t(e_k)=N$ であるような歩道を頂点 $0$ から頂点 $N$ への歩道という.

歩道 $W=(e_1, \dots, e_k)$ に対して, 辺 $e$ の長さを $l(e)$ としたとき, 歩道 $W$ の長さ $l(W)$ を, $l(W)=\sum_{i=1}^k l(e_i)$ とする.

制約

  • $1 \leq N \leq 10^5$
  • $1 \leq M \leq 2 \times 10^5$
  • $0 \leq u_j, v_j \leq N$
  • $u_j \neq v_j$
  • $1 \leq l_j \leq 10^9$
  • $1 \leq a_j \leq 10^9$
  • 入力は全て整数である.

入力

$N\ M$
$u_1\ v_1\ l_1\ a_1$
$\vdots$
$u_M\ v_M\ l_M\ a_M$

出力

頂点 $0$ から頂点 $N$ への歩道の長さの総和が有限ならば, その総和を $10^9+7$ で割った余りを出力せよ. もし, 無限ならば, INF と出力せよ. どちらにせよ, 最後に改行を忘れないこと.

サンプル

サンプル1
入力
3 4
0 1 2 1
1 2 1 1
2 3 3 1
0 3 4 1
出力
10

$0 \to 1 \to 2 \to 3$ と辿る長さ $6$ の歩道と, $0 \to 3$ と辿る長さ $4$ の歩道の2つの長さの総和は $10$ である.

サンプル2
入力
3 4
0 1 1 1
1 2 1 1
2 1 1 1
2 3 1 1
出力
INF

任意の正の整数 $n$ に対して, 頂点 $1$ と頂点 $2$ を $n$ 回往復する歩道が存在する. よって, 長さの総和は無限になる.

サンプル3
入力
1 2
0 1 3 2
0 1 4 3
出力
18

2頂点間を結ぶ辺の長さは一意とは限らない.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。