← 返回题目列表

AtCoder · kupc2014_i

I. 雨

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

现在是30世纪,狐狸Shieru是雨神,控制着KUPC国家的降雨量。 KUPC国家是 它被分为 N 区域,Shieru必须让每个区域的降雨均匀。 Shieru施展咒语,让天下雨。 咒语是 M 有不同的类型,每种 它们的编号最大为 1 到 M 。 i 第二个法术有一个潮湿的区域。 a_i 和干旱地区 指定 b_i , a_i 地区有雨。 2 下车,b_i 地区没有下雨, 除此之外 N-2 部分地区有雨 1 秋天。 另外, 执行第i 个咒语 需要 d_i 天。

首先, K 法术 (c_1,...,c_{K}) 被执行。 希鲁就是那个 在执行 K 法术后,你想要执行几个法术来均衡每个区域的总降雨量。 执行 K 咒语后,打印均衡每个区域总降雨量所需的最少天数。 然而,如果不可能使每个地区的总降雨量相等, -1 。 它是一个

入力形式

测试用例按以下格式给出。

N M K
c_1 … c_{K}
a_1 b_1 d_1
…
a_M b_{M} d_M

出力形式

输出是一个表示最小天数的整数,或者 -1 的, 仅由1 行组成。

制約

  • 2 \leq N \leq 10000
  • 1 \leq M \leq 20000
  • 1 \leq K \leq 15
  • 1 \leq c_i \leq M
  • 1 \leq a_i \leq N
  • 1 \leq b_i \leq N
  • a_i \neq b_i
  • 1 \leq d_i \leq 3
  • 所有输入值都是整数。

针对该问题的判断设置了一组30分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。 通过执行

  • K = 1

入出力例

入力例1

9 10 4
1 2 4 6
1 2 1
2 3 2
3 4 3
4 5 1
5 1 2
6 7 3
7 8 2
8 6 3
8 9 1
9 6 1

出力例1

9

3,5,7,9,10咒语,你可以在9天内使每个区域降下相同数量的降雨。

入力例2

3 3 1
1
1 2 1
1 3 2
2 3 3

出力例2

-1

入力例3

2 2 2
1 1
1 2 2
2 1 3

出力例3

6

入力例4

2 2 2
1 2
1 2 2
2 1 3

出力例4

0

入力例5

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

出力例5

6