N - 何かグラフの問題 Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

太郎くんにN頂点M辺の有向グラフが与えられた。 このグラフには多重辺があるかもしれないが、自己ループとなる辺は張られていない。 また、辺eに対してc_eが与えられている。

太郎くんは各頂点vに対して定められるN個の変数a_vと変数Tに実数値を割り当てることができる。 このとき、次の条件を満たしつつTを最小化することを考えたい。

  • 条件 : 任意の辺eに対してその始点をu, 終点をwとすればa_u + c_e \leq a_w + Tを満たす。

さらに、先ほど与えられたa_vはいくつかの頂点vに対しては既に値が固定されており、この変数には例外的に値を割り当てることができない。

Tとして取りうる最小値を実数で出力せよ。どこまでも小さくできるときは"#"の1文字を出力せよ。

入力

入力は以下の形式で標準入力から与えられる。

N M K
v_1 val_1
v_2 val_2
:
v_K val_K
u_1 w_1 c_1
u_2 w_2 c_2
:
u_M w_M c_M
  • 入力における数はすべて整数である
  • 1 行目には N(1 \leq N \leq 2,000),M(1 \leq M \leq 2,000),K(0 \leq K \leq N) が空白区切りで与えられる。N,Mはそれぞれ与えられるグラフの頂点数と辺数を表している。 Kはaの値が既に決定されている頂点数を表す。
  • 次の K 行には、既にaの値が決まっている頂点の情報が与えられる。 このK行のうちi行目にはv_i (1 \leq v_i \leq N), val_i (-10^5 \leq val_i \leq 10^5)が空白区切りで与えられる。 これはa_{v_i} = val_iであることを表している。また、v_i は相異なると仮定してよい
  • 次の M 行にはグラフの辺情報が与えられる。このM行のうちi行目にはu_i(1 \leq u_i \leq N) w_i(1 \leq w_i \leq N) c_i(-10^5 \leq c_i \leq 10^5)　が空白区切りで与えられる。また、u_i \neq v_iをみたす。これは有向辺が頂点u_iからw_iへ張られていることを表している。

出力

問題文にしたがってTの最小値を実数で出力せよ。無限に小さくできるときは"#"の1文字を出力せよ。

答えが実数であるときには誤差は絶対誤差または相対誤差で10^{-5}の差まで許容される

出力は標準出力に行い、末尾に改行を入れること。

入力例1

3 3 0
1 2 3
2 3 4
3 1 5

出力例1

4.000000
  • aはa_1=0, a_2=-1, a_3=-1 と割り当てれば良い

入力例2

3 2 3
1 1
2 2
3 3
1 2 3
2 3 4

出力例2

3.000000
  • aの値がすべて決まっているので条件を満たすTの最小値はすぐに決まる。

入力例3

10 8 0
8 7 5
6 8 -3
10 1 2
1 5 -8
4 7 -2
5 4 -7
10 5 1
1 5 7

出力例3

#
  • 多重辺を持つ場合もあるので注意すること