問題一覧 > 教育的問題

No.2915 辺更新価値最大化

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : 👑 p-adicp-adic / テスター : ShirotsumeShirotsume
2 ProblemId : 10650 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-31 08:03:26

問題文

入力の最初に $3$ 個の正整数 $N, M, Q$ が与えられます。

ある村には $N$ 個の広場と、それらを結ぶ $M$ 本の一方通行の道があります。

広場は $N$ 以下の各正整数 $i$ で番号付けられ広場 $i$ と呼ばれます。

道は $M$ 以下の各正整数 $j$ で番号付けられ道 $j$ と呼ばれ、道 $j$ は広場 $u_j$ から広場 $v_j$ へ向かっています（$u_j, v_j$ は相異なる $N$ 以下の正整数）。

　

直進大好きbotはこの村の道を直進するのが大好きなbotです。直進大好きbotはどの道を直進したかに従って爽快度という整数値が変化します。

具体的には、$M$ 以下の各正整数 $j$ に対し、直進大好きbotが道 $j$ を広場 $u_j$ から広場 $v_j$ に向かって直進した時は爽快度に（非負とは限らない）整数 $w_j$ が加算されます。

ただし、ある広場から出発して道だけを直進して元の広場に戻ってくる経路であって、最終的な爽快度が出発時点の爽快度より真に大きくなるものは存在しないことが保証されています。

　

最初はどの道も壊れていないのですが、以下で説明する $Q$ 個のクエリにより道が壊れたり直ったりします。

各クエリは $M$ 以下の正整数 $j$ として与えられます。クエリが $j$ である時、そのクエリは次のように処理します。

  1. まず、道 $j$ が壊れていなければ道 $j$ を壊し、道 $j$ が壊れていれば道 $j$ を直す。
  2. 次に、壊れていない道だけを直進して広場 $1$ から広場 $N$ へ到達する経路が存在するか否かを判定する。
  3. そして存在する時は、そのような経路に沿って直進大好きbotが爽快度 $0$ の状態から道を直進していった時の最終的な爽快度の最大値を求める。

また2,3の結果をこのクエリに対する回答と呼びます。

　

全てのクエリを与えられた順に処理してください。

入力

$Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリを $j_q$ と置きます。

この時、入力は以下の形式で標準入力から $2 + M$ 行で与えられます：

  • $1$ 行目に $N, M, Q$ が半角空白区切りで与えられます。
  • $M$ 以下の各正整数 $j$ に対し、$1 + j$ 行目に $u_j , v_j , w_j$ が半角空白区切りで与えられます。
  • $2 + M$ 行目に $Q$ 以下の各正整数 $q$ に対する $j_q$ が $q$ の小さい順に半角空白区切りで与えられます。
$N$ $M$ $Q$
$u_1$ $v_1$ $w_1$
$\vdots$
$u_M$ $v_M$ $w_M$
$j_1$ $\cdots$ $j_Q$

制約

入力は以下の制約を満たします：

  • $N$ は $2 \leq N \leq 10^3$ を満たす整数である。
  • $M$ は $1 \leq M \leq 10^3$ を満たす整数である。
  • $M$ 以下の任意の正整数 $j$ に対し、
    • $u_j, v_j$ は $1 \leq u_j \leq N$ かつ $1 \leq v_j \leq N$ かつ $u_j \neq v_j$ を満たす整数である。
    • $w_j$ は $- 10^3 \leq w_j \leq 10^3$ を満たす整数である。
  • ある広場から出発して道だけを直進して元の広場に戻ってくる経路であって、最終的な爽快度が出発時点の爽快度より真に大きくなるものは存在しない。
  • $Q$ は $1 \leq Q \leq 10^3$ を満たす整数である。
  • $Q$ 以下の任意の正整数 $q$ に対し、$j_q$ は $1 \leq j_q \leq M$ を満たす整数である。

出力

$Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリに対する回答を以下の形式で $q$ 行目に出力してください。

  • 壊れていない道だけを直進して広場 $1$ から広場 $N$ へ到達する経路が存在するならば、そのような経路に沿って直進大好きbotが爽快度 $0$ の状態から道を直進していった時の最終的な爽快度の最大値を出力してください。
  • そうでないならば、NaNと出力してください。

なお前者のケースにおいて最大値が存在することは、この問題の制約下で証明可能です。

最後に改行してください。

サンプル

サンプル1
入力
2 1 2
1 2 0
1 1
出力
NaN
0

広場 $1,2$ があります。最初はこれらが道 $1$ により

$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 $

と結ばれている状態です。

　

$1$ 回目のクエリの値は $j_1 = 1$ です。まず道 $1$ を壊します。すると壊れていない道が存在しなくなるので、壊れていない道だけを直進して広場 $1$ から広場 $2$ へ到達する経路は存在しません。

従ってNaNを出力します。

　

$2$ 回目のクエリの値は $j_2 = 1$ です。まず道 $1$ を直し、広場が

$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 $

と結ばれている状態になります。そして広場 $1$ から広場 $2$ へ向かう経路は

$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 $

のみであり、この経路で広場 $2$ に到達した時の直進大好きbotの爽快度は $0$ です。

　

今回は $Q = 2$ なので、これにて全てのクエリが処理できました。

サンプル2
入力
3 4 2
1 2 0
2 3 1
3 2 -3
2 3 2
3 4

このように複数の道が同じ広場の組を結びうることに注意してください。

出力
2
1

広場 $1,2,3$ があります。最初はこれらが道 $1,2,3,4$ により

$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \begin{array}{c} \displaystyle \stackrel{w_2 = 1}{\longrightarrow} \\ \displaystyle \stackrel{w_3 = -3}{\longleftarrow} \\ \displaystyle \stackrel{w_4 = 2}{\longrightarrow} \end{array} 3 $

と結ばれている状態です。

　

$1$ 回目のクエリの値は $j_1 = 3$ です。まず道 $3$ を壊し、広場が

$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \begin{array}{c} \displaystyle \stackrel{w_2 = 1}{\longrightarrow} \\ \displaystyle \stackrel{w_4 = 2}{\longrightarrow} \end{array} 3 $

と結ばれている状態になります。そして広場 $1$ から広場 $3$ へ向かう経路には

$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \stackrel{w_2 = 1}{\longrightarrow} 3 $

と

$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \stackrel{w_4 = 2}{\longrightarrow} 3 $

の $2$ つがあり、これらの経路で広場 $3$ に到達した時の直進大好きbotの爽快度はそれぞれ $0 + 1 = 1$ と $0 + 2 = 2$ です。

　

$2$ 回目のクエリの値は $j_2 = 4$ です。まず道 $4$ を壊し、広場が

$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \stackrel{w_2 = 1}{\longrightarrow} 3 $

と結ばれている状態になります。そして広場 $1$ から広場 $3$ へ向かう経路は

$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \stackrel{w_2 = 1}{\longrightarrow} 3 $

のみであり、この経路で広場 $3$ に到達した時の直進大好きbotの爽快度は $0 + 1 = 1$ です。

　

今回は $Q = 2$ なので、これにて全てのクエリが処理できました。

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

このように $M$ 以下の正整数 $j$ に対する $w_j$ の値が負になりえることに注意してください。

出力
-3
1

広場 $1,2,3,4$ があります。最初はこれらが道 $1,2,3,4$ により

$\displaystyle \begin{array}{rcl} \displaystyle 1 &\displaystyle \stackrel{w_4 = 1}{\longrightarrow} &\displaystyle 4 \\ \displaystyle {}_{w_1 = -1} \downarrow &\displaystyle &\displaystyle \uparrow_{w_3 = -1} \\ \displaystyle 2 &\displaystyle \stackrel{w_2 = -1}{\longrightarrow} &\displaystyle 3 \end{array} $

と結ばれている状態です。

　

$1$ 回目のクエリの値は $j_1 = 4$ です。まず道 $4$ を壊し、広場が

$\displaystyle \begin{array}{rcl} \displaystyle 1 &\displaystyle &\displaystyle 4 \\ \displaystyle {}_{w_1 = -1} \downarrow &\displaystyle &\displaystyle \uparrow_{w_3 = -1} \\ \displaystyle 2 &\displaystyle \stackrel{w_2 = -1}{\longrightarrow} &\displaystyle 3 \end{array} $

と結ばれている状態になります。そして広場 $1$ から広場 $4$ へ向かう経路には

$\displaystyle 1 \stackrel{w_1 = -1}{\longrightarrow} 2 \stackrel{w_2 = -1}{\longrightarrow} 3 \stackrel{w_3 = -1}{\longrightarrow} 4 $

のみがあり、この経路で広場 $4$ に到達した時の直進大好きbotの爽快度は $(-1) + (-1) + (-1) = -3$ です。

　

$2$ 回目のクエリの値は $j_2 = 4$ です。まず道 $4$ を直し、広場が

$\displaystyle \begin{array}{rcl} \displaystyle 1 &\displaystyle \stackrel{w_4 = 1}{\longrightarrow} &\displaystyle 4 \\ \displaystyle {}_{w_1 = -1} \downarrow &\displaystyle &\displaystyle \uparrow_{w_3 = -1} \\ \displaystyle 2 &\displaystyle \stackrel{w_2 = -1}{\longrightarrow} &\displaystyle 3 \end{array} $

と結ばれている状態になります。そして広場 $1$ から広場 $4$ へ向かう経路には

$\displaystyle 1 \stackrel{w_4 = 1}{\longrightarrow} 4 $

と

$\displaystyle 1 \stackrel{w_1 = -1}{\longrightarrow} 2 \stackrel{w_2 = -1}{\longrightarrow} 3 \stackrel{w_3 = -1}{\longrightarrow} 4 $

の $2$ つがあり、これらの経路で広場 $4$ に到達した時の直進大好きbotの爽快度はそれぞれ $1$ と $(-1) + (-1) + (-1) = -3$ です。

　

今回は $Q = 2$ なので、これにて全てのクエリが処理できました。

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