問題一覧 > 通常問題

No.2477 Drifting

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 : だれ / テスター : akakimidori りあん tsutaj beet tute7627 👑 SPD_9X2 nok0 rin204 momoyuu KKT89
ProblemId : 9863 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-10-14 00:37:06

問題文

頂点に $1$ から $N$ 、辺に $1$ から $M$ の番号が付いた $N$ 頂点 $M$ 辺の重み付き有向グラフが与えられます。$i\ (1\leq i \leq M)$ 番目の辺は頂点 $u_i$ から頂点 $v_i$ $(u_i \lt v_i)$ へ張られていて、辺の重みは $w_i$ です。

また、整数の三つ組が $K$ 個与えられます。$i\ (1\leq i \leq K)$ 番目の三つ組は $(a_i,b_i,c_i)\ (a_i < b_i < c_i)$ です。

あなたははじめ頂点 $1$ にいて、辺が張られた頂点に移動することを繰り返して頂点 $N$ に移動したいです。

ただし、全ての $i\ (1\leq i \leq K)$ に対して、頂点 $a_i$ の次に頂点 $b_i$ に移動した場合、次は頂点 $c_i$ 以外の頂点に移動しなくてはなりません。

頂点 $N$ へ移動できるか判定してください。移動できる場合、通る辺の重みの総和の最小値も求めてください。

制約

  • 入力される値はすべて整数
  • $3\leq N\leq 2\times 10^5$
  • $0\leq M\leq 2\times 10^5$
  • $1\leq u_i\lt v_i \leq N$ $(1\leq i\leq M)$
  • $i\neq j \Rightarrow (u_i, v_i)\neq (u_j, v_j)$ $(1\leq i, j\leq M)$
  • $1\leq w_i\leq 10^9$ $(1\leq i\leq M)$
  • $0\leq K\leq 2\times 10^5$
  • $1\leq a_i\lt b_i\lt c_i\leq N$ $(1\leq i\leq K)$

入力

$N$ $M$
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
$\vdots$
$u_M$ $v_M$ $w_M$
$K$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
$\vdots$
$a_K$ $b_K$ $c_K$

出力

頂点 $N$ へ移動できない場合、-1 を出力せよ。そうでない場合、通る辺の重みの総和の最小値を出力せよ。

サンプル

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

$1 \to 3\to 4$ と移動するのが最適です。

サンプル2
入力
7 8
1 2 5
1 3 2
2 4 1
3 4 1
4 5 6
4 6 2
5 7 1
6 7 1
2
2 4 5
3 4 6
出力
9

$1\to 2\to 4\to 6\to 7$ と移動するのが最適です。

サンプル3
入力
3 2
1 2 1
2 3 1
1
1 2 3
出力
-1

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