AT_ttpc2015_n 何かグラフの問題

太郎君得到了一个有 $N$ 个顶点、$M$ 条边的有向图。该图可能包含重边，但没有自环。此外，每条边 $e$ 都给定了一个权值 $c_e$。 太郎君可以为每个顶点 $v$ 分别分配 $N$ 个变量 $a_v$ 的实数值，以及一个变量 $T$ 的实数值。此时，他希望在满足以下条件的前提下，使 $T$ 的值最小。 - 条件：对于任意一条边 $e$，设其起点为 $u$，终点为 $w$，则必须满足 $a_u + c_e \leq a_w + T$。 此外，对于某些顶点 $v$，$a_v$ 的值已经被固定，不能再分配其它值。 请输出 $T$ 能取得的最小值。如果 $T$ 可以无限减小，则输出一个字符“#”。

输入通过标准输入给出，格式如下： > $N$ $M$ $K$ > $v_1$ $val_1$ > $v_2$ $val_2$ > $\vdots$ > $v_K$ $val_K$ > $u_1$ $w_1$ $c_1$ > $u_2$ $w_2$ $c_2$ > $\vdots$ > $u_M$ $w_M$ $c_M$ - 所有输入的数均为整数。 - 第 1 行包含 $N(1 \leq N \leq 2000)$、$M(1 \leq M \leq 2000)$、$K(0 \leq K \leq N)$，分别表示图的顶点数、边数，以及 $a$ 的值已被固定的顶点数。 - 接下来的 $K$ 行，每行包含 $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$ 行，每行包含 $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$ 指向 $w_i$ 的有向边，权值为 $c_i$。保证 $u_i \neq w_i$。

请根据题意输出 $T$ 的最小值。如果 $T$ 可以无限减小，则输出一个字符“#”。 如果答案为实数，允许绝对误差或相对误差在 $10^{-5}$ 以内。 输出需以换行符结尾。

### 样例解释 1 - 可以将 $a$ 赋值为 $a_1=0,\ a_2=-1,\ a_3=-1$。 ### 样例解释 2 - 所有 $a$ 的值都已确定，因此满足条件的 $T$ 的最小值可以直接确定。 ### 样例解释 3 - 需要注意可能存在重边的情况。 由 ChatGPT 4.1 翻译