U66530.汉尼拔

提高+/省选-

通过率：0%

时间限制：0.40s ~ 0.59s

内存限制：512MB

题目描述

汉尼拔喜欢饮食。但是，食物有很多不同种类，汉尼拔需要每种食物都吃至少一个才能营养均衡。有些食物间有一条路径，汉尼拔可以通过路径从一个食物移动到另一个食物。

输入格式

第一行输入n,m,k，（1<=n<=500,1<=m<= $10^5$ ,1<=k<=12）分别代表食物的个数、路径的个数、食物的种类数。
接下来1行，输入n个整数，代表第i个食物的种类。
接下来m行，每行输入三个整数a,b,c，代表第a和第b个食物间有一条长度为c的路径。

输出格式

请帮汉尼拔找出若干条连在一起的路径，使得在这若干条路径所连的节点中包含了每一种食物至少一个，并输出在此前提下这些路径之和的最小值。做出来之后汉尼拔会吃掉你。

输入输出样例

输入#1

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

输出#1

输入#2

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

输出#2

输入#3

54 114 12
5 1 6 9 4 3 9 12 7 9 5 5 4 4 11 1 8 4 9 6 11 8 1 8 7 2 2 11 3 3 8 5 10 6 1 9 2 2 12 9 7 3 8 9 4 3 6 8 5 5 12 7 10 4 50 25 20
1 33 98
2 33 30
10 53 62
31 20 47
37 35 20
34 49 42
6 15 1
44 14 37
22 9 95
36 44 19
48 44 36
35 49 46
18 25 14
47 8 56
29 37 76
35 20 97
8 54 98
4 22 31
11 32 24
54 7 94
16 23 4
25 48 78
12 1 63
34 35 54
23 20 94
9 52 90
54 30 47
46 6 99
35 46 13
18 36 47
53 36 65
5 6 1
41 53 91
52 3 98
35 44 21
47 32 90
9 19 17
19 53 48
37 46 1
21 32 48
32 5 96
17 18 26
31 38 47
43 26 15
30 24 19
45 11 84
5 49 55
35 25 20
29 53 37
11 52 30
31 21 95
38 52 96
33 9 27
49 34 68
2 51 13
7 48 59
24 51 57
29 32 8
48 45 63
20 20 94
28 29 57
45 28 31
25 32 60
7 28 1
28 10 81
18 3 95
10 51 44
52 46 66
38 15 44
32 48 59
39 33 89
47 27 23
27 7 10
12 49 85
48 26 49
31 10 58
21 13 73
29 21 39
24 41 3
3 17 75
44 26 91
34 33 8
36 10 89
40 23 60
16 10 15
8 51 21
3 22 20
48 39 17
6 27 65
22 34 66
3 32 89
51 24 11
51 42 38
49 21 76
23 24 7
45 7 71
39 33 37
27 2 53
27 3 52
13 43 96
38 3 73
52 21 7
44 31 6
15 19 62
9 48 61
27 42 23
48 2 76
37 9 79
40 14 93
51 13 92
49 7 96
51 43 57
9 50 44

输出#3

输入#4

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

输出#4

说明/提示

煤油

首页