AT_ttpc2015_n 何かグラフの問題

[problemUrl]: https://atcoder.jp/contests/ttpc2015/tasks/ttpc2015_n 太郎くんに$ 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} $の差まで許容される 出力は標準出力に行い、末尾に改行を入れること。

### Sample Explanation 1 \- $ a $は$ a_1=0,\ a_2=-1,\ a_3=-1 $ と割り当てれば良い ### Sample Explanation 2 \- $ a $の値がすべて決まっているので条件を満たす$ T $の最小値はすぐに決まる。 ### Sample Explanation 3 \- 多重辺を持つ場合もあるので注意すること