Posted on 2008-05-04 22:29
superman 阅读(339)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1085 C++ 00:00.00 872K */
2 #include <queue>
3 #include <string>
4 #include <sstream>
5 #include <iostream>
6
7 using namespace std;
8
9 int n, et, del;
10 bool map[10][10];
11
12 bool visited[10];
13 void dfs(int p)
14 {
15 visited[p] = true;
16 for(int i = 0; i < n; i++)
17 if(i != del && map[p][i] && visited[i] == false)
18 dfs(i);
19 }
20
21 void spfa(int s, int d[])
22 {
23 for(int i = 0; i < n; i++)
24 d[i] = INT_MAX;
25 queue <int> q;
26 q.push(s);
27 d[s] = 0;
28 while(q.empty() == false)
29 {
30 int u = q.front(); q.pop();
31 for(int v = 0; v < n; v++)
32 if(map[v][u] && d[u] + 1 < d[v])
33 {
34 d[v] = d[u] + 1;
35 q.push(v);
36 }
37 }
38 }
39
40 int main()
41 {
42 int N;
43 cin >> N;
44
45 while(N--)
46 {
47 memset(map, 0, sizeof(map));
48
49 cin >> n >> et;
50
51 int s, t;
52 string str;
53 getline(cin, str);
54
55 while(true)
56 {
57 if(getline(cin, str) == false || str == "") break;
58 stringstream in(str);
59 in >> s >> t; map[s][t] = true;
60 }
61
62 int d[10];
63 spfa(et, d);
64
65 bool x[10] = { false };
66 while(true)
67 {
68 int min = INT_MAX;
69 for(int i = 0; i < n; i++)
70 if(i != et && x[i] == false)
71 if(d[i] < min)
72 {
73 min = d[i];
74 del = i;
75 }
76 if(min == INT_MAX)
77 {
78 cout << "Put guards in room " << 0 << '.' << endl; break;
79 }
80 memset(visited, false, sizeof(visited));
81 x[del] = true;
82 dfs(0);
83
84 if(visited[et] == false)
85 {
86 cout << "Put guards in room " << del << '.' << endl; break;
87 }
88 }
89 if(N)
90 cout << endl;
91 }
92
93 return 0;
94 }
95