簡單題,非常簡單直觀的BFS.
Code
1
#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6const int NODE = 20;
7vector<vector<int> > g(20);
8
9int search(int s, int e)
10
{
11
queue<int> q;
12 q.push(s);
13 bool visited[NODE];
14 int high[NODE];
15 memset(visited, false, NODE);
16 memset(high, -1, NODE);
17
18 visited[s] = true;
19 high[s] = 0;
20 while(!q.empty())
21
{
22 int node = q.front();
23 q.pop();
24
25 vector<int>::iterator end = g[node].end();
26 for(vector<int>::iterator ite = g[node].begin(); ite != end; ++ite)
27 {
28 if(visited[*ite] == false)
29 {
30 q.push(*ite);
31 visited[*ite] = true;
32 high[*ite] = high[node] + 1;
33 if(*ite == e)
34 return high[*ite];
35
}
36 }
37 }
38
}
39
40int _tmain(int argc, _TCHAR* argv[])
41{
42 int cases(0);
43 while(true)
44 {
45 for(int i = 0; i < NODE; ++i)
46 {
47 g[i].clear();
48 }
49
50 for(int i = 0; i < NODE - 1; ++i)
51 {
52 int n, t;
53 if(!(cin >> n))
54 return 0;
55 while(n--)
56 {
57 cin >> t;
58 g[i].push_back(t - 1);
59 g[t - 1].push_back(i);
60 }
61 }
62
63 int s, start, end;
64 cin >> s;
65 cout << "Test Set #" << ++cases << endl;
66 for(int i = 0; i < s; ++i)
67 {
68 cin >> start >> end;
69 cout << start << " to " << end << ": " << search(start - 1, end - 1) << endl;
70 }
71 cout << endl;
72 }
73 return 0;
74}
75
76posted on 2009-03-31 20:58
肖羽思 閱讀(994)
評論(1) 編輯 收藏 引用 所屬分類:
ZOJ