题目详情题解（0）讨论（0）提交记录（0）

AT_ttpc2015_n.何かグラフの問題

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

太郎君得到了一个有 NN 个顶点、MM 条边的有向图。该图可能包含重边，但没有自环。此外，每条边 ee 都给定了一个权值 cec_e。

太郎君可以为每个顶点 vv 分别分配 NN 个变量 ava_v 的实数值，以及一个变量 TT 的实数值。此时，他希望在满足以下条件的前提下，使 TT 的值最小。

  • 条件：对于任意一条边 ee，设其起点为 uu，终点为 ww，则必须满足 au+ce≤aw+Ta_u + c_e \leq a_w + T。

此外，对于某些顶点 vv，ava_v 的值已经被固定，不能再分配其它值。

请输出 TT 能取得的最小值。如果 TT 可以无限减小，则输出一个字符“#”。

输入格式

输入通过标准输入给出，格式如下：

NN MM KK
v1v_1 val1val_1
v2v_2 val2val_2
⋮\vdots
vKv_K valKval_K
u1u_1 w1w_1 c1c_1
u2u_2 w2w_2 c2c_2
⋮\vdots
uMu_M wMw_M cMc_M

  • 所有输入的数均为整数。
  • 第 1 行包含 N(1≤N≤2000)N(1 \leq N \leq 2000)、M(1≤M≤2000)M(1 \leq M \leq 2000)、K(0≤K≤N)K(0 \leq K \leq N)，分别表示图的顶点数、边数，以及 aa 的值已被固定的顶点数。
  • 接下来的 KK 行，每行包含 vi (1≤vi≤N)v_i\ (1 \leq v_i \leq N) 和 vali (−105≤vali≤105)val_i\ (-10^5 \leq val_i \leq 10^5)，表示 avi=valia_{v_i} = val_i。保证 viv_i 互不相同。
  • 接下来的 MM 行，每行包含 ui(1≤ui≤N)u_i(1 \leq u_i \leq N)、wi(1≤wi≤N)w_i(1 \leq w_i \leq N)、ci(−105≤ci≤105)c_i(-10^5 \leq c_i \leq 10^5)，表示有一条从 uiu_i 指向 wiw_i 的有向边，权值为 cic_i。保证 ui≠wiu_i \neq w_i。

输出格式

请根据题意输出 TT 的最小值。如果 TT 可以无限减小，则输出一个字符“#”。

如果答案为实数，允许绝对误差或相对误差在 10−510^{-5} 以内。

输出需以换行符结尾。

输入输出样例

  • 输入#1

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

    输出#1

    4.000000

  • 输入#2

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

    输出#2

    3.000000

  • 输入#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

    #

说明/提示

样例解释 1

  • 可以将 aa 赋值为 a1=0, a2=−1, a3=−1a_1=0,\ a_2=-1,\ a_3=-1。

样例解释 2

  • 所有 aa 的值都已确定，因此满足条件的 TT 的最小值可以直接确定。

样例解释 3

  • 需要注意可能存在重边的情况。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页