Posted on 2008-04-21 22:55
superman 阅读(230)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1127 C++ 00:00.00 840K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m;
7 int len[26][26];
8 bool map[26][26], visited[26];
9
10 void dfs(int s, int p, int cnt)
11 {
12 visited[p] = true;
13 for(int i = 0; i < n; i++)
14 if(map[p][i] && visited[i] == false)
15 {
16 len[s][i] = cnt + 1;
17 dfs(s, i, cnt + 1);
18 }
19 }
20
21 int main()
22 {
23 char source;
24 cin >> n >> source >> m;
25
26 char s, t;
27 while(cin >> s >> t)
28 s -= 'A', t -= 'A', map[s][t] = map[t][s] = true;
29
30 for(int i = 0; i < n; i++)
31 {
32 memset(visited, false, sizeof(visited));
33 dfs(i, i, 0);
34 }
35
36 m--;
37 cout << "Program 8 by team X" << endl;
38 cout << source; source -= 'A';
39
40 bool fortified[26] = {false};
41 fortified[source] = true;
42
43 while(m--)
44 {
45 int max = 0, idx;
46 for(int i = 0; i < n; i++)
47 if(fortified[i] == false)
48 {
49 int minDist = INT_MAX;
50
51 for(int j = 0; j < n; j++)
52 if(fortified[j])
53 minDist <?= len[i][j];
54 if(max < minDist)
55 {
56 max = minDist;
57 idx = i;
58 }
59 }
60 fortified[idx] = true;
61 cout << ' ' << char(idx + 'A');
62 }
63 cout << endl << "End of program 8 by team X" << endl;
64
65 return 0;
66 }
67