← 返回题目列表

Codeforces · 400/D

D. 迪马和细菌

中文机器翻译题面 查看原题

Dima 开始研究细菌生物学,通过实验,他发明了 k 种细菌。总体而言,他的实验室现在有n个细菌,i型细菌的数量等于ci。为了方便起见,我们假设所有细菌都从 1 到 n 编号。 ci 型细菌的编号从 $$(\sum_{k=1}^{i-1} c_k) + 1$$ 到 $$\sum_{k=1}^{i} c_k$$。

在特殊设备的帮助下,迪马可以将某些细菌的能量转移到其他细菌中。当然,此类设备的使用并不是免费的。迪马知道多种将能量从某些细菌转移到另一种细菌的方法。编号为 i 的方式可以用整数 ui、vi 和 xi 来描述,这意味着这种方式允许将能量从编号为 ui 的细菌转移到编号为 vi 的细菌,反之亦然(对于 xi 美元)。

如果有一种方法(可能是非直接的)以零成本将能量从特定类型的任何细菌转移到相同类型的任何其他细菌(在相同类型的任意两个细菌之间),则迪马的厨师(Inna)称类型分布是正确的。

至于正确的类型分布,移动能量的成本仅取决于细菌的类型,帮助Inna确定类型分布是否正确?如果是,则打印大小为 k × k 的矩阵 d。该矩阵的单元 d[i][j] 必须等于从 i 型细菌到 j 型细菌的能量转移的最小可能成本。

输入

第一行包含三个整数 n、m、k (1 ≤ n ≤ 105;0 ≤ m ≤ 105;1 ≤ k ≤ 500)。下一行包含 k 个整数 c1, c2, ..., ck (1 ≤ ci ≤ n)。接下来的 m 行中的每一行都包含三个整数 ui, vi, xi (1 ≤ ui, vi ≤ 105; 0 ≤ xi ≤ 104)。保证 $$\sum_{i=1}^{k} c_i = n$$。

输出

如果 Dima 的类型分布正确,则打印字符串 «Yes»,然后 k 行:在第 i 行中打印整数 d[i][1], d[i][2], ..., d[i][k] (d[i][i] = 0)。如果没有办法将能量从细菌 i 转移到细菌 j,则适当的 d[i][j] 必须等于 -1。如果类型分布不正确,则打印“否”。

示例

输入 #1

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

输出 #1

Yes
0 2
2 0

输入 #2

3 1 2
2 1
1 2 0

输出 #2

Yes
0 -1
-1 0

输入 #3

3 2 2
2 1
1 2 0
2 3 1

输出 #3

Yes
0 1
1 0

输入#4

3 0 2
1 2

输出#4

No