Posted on 2009-05-19 10:30
superman 阅读(259)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <queue>
2 #include <iostream>
3
4 using namespace std;
5
6 int cowNum;
7 int pastureNum;
8 int pathNum;
9 int map[800][800];
10
11 int CowsInThePasture[800];
12
13 struct
14 {
15 int x[800][800];
16 int c[800];
17
18 } AdjList;
19
20 int main()
21 {
22 freopen("butter.in", "r", stdin);
23 freopen("butter.out", "w", stdout);
24
25 cin >> cowNum >> pastureNum >> pathNum;
26 for (int i = 0; i < cowNum; i++)
27 {
28 int t;
29 cin >> t;
30 CowsInThePasture[t - 1]++;
31 }
32
33 for (int i = 0; i < pastureNum; i++)
34 for (int j = 0; j < pastureNum; j++)
35 map[i][j] = INT_MAX;
36
37 int s, t, l;
38 for (int i = 0; i < pathNum; i++)
39 {
40 cin >> s >> t >> l;
41 map[s - 1][t - 1] <?= l;
42 map[t - 1][s - 1] <?= l;
43 }
44
45 for (int i = 0; i < pastureNum; i++)
46 for (int j = 0; j < pastureNum; j++)
47 if (map[i][j] != INT_MAX)
48 AdjList.x[i][AdjList.c[i]++] = j;
49
50 int ans = INT_MAX;
51 for (int k = 0; k < pastureNum; k++)
52 {
53 int d[800];
54 for (int i = 0; i < pastureNum; i++)
55 d[i] = INT_MAX;
56 d[k] = 0;
57
58 queue<int> q;
59 q.push(k);
60
61 bool inqueue[800] = { false };
62 inqueue[k] = true;
63
64 while (q.empty() == false)
65 {
66 int s = q.front(); q.pop();
67
68 for (int i = 0; i < AdjList.c[s]; i++)
69 {
70 int t = AdjList.x[s][i];
71 if (map[s][t] != INT_MAX && d[s] + map[s][t] < d[t])
72 {
73 d[t] = d[s] + map[s][t];
74 if (inqueue[t] == false)
75 {
76 inqueue[t] = true;
77 q.push(t);
78 }
79 }
80 }
81
82 inqueue[s] = false;
83 }
84
85 int sum = 0;
86 for (int i = 0; i < pastureNum; i++)
87 if (CowsInThePasture[i])
88 sum += d[i] * CowsInThePasture[i];
89
90 ans <?= sum;
91 }
92
93 cout << ans << endl;
94
95 return 0;
96 }
97