問題文
致太郎君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的最小可能值打印为实数。如果可以使其尽可能小,则输出单个字符“#”。
入力
输入是按以下格式从标准输入给出的。
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的最小值打印为实数。如果可以无限小,则输出单个字符“#”。
当答案为实数时,误差为绝对误差或相对误差。 允许差异最大为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
#
- 请注意,可能存在多个边缘。