← 返回题目列表

AtCoder · ttpc2015_n

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的最小可能值打印为实数。如果可以使其尽可能小,则输出单个字符“#”。


入力

输入是按以下格式从标准输入给出的。

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

#
  • 请注意,可能存在多个边缘。