BFS
1 #include <iostream>
2 using namespace std;
3 const int OO=1000000;
4 int n;
5 int list[1011][2];
6 int bus[2011][2011];
7 int num,sa,sb;
8 int alist[2011];
9 int ans=OO,apos=0;
10 bool v[2011];
11 int q[2011][2],st,en,deep=OO;
12 int pre[2011],enpos;
13
14 void bfs(int x){
15 st=0;
16 en=0;
17 for (int i=1;i<=bus[x][0];++i){
18 ++en;
19 q[en][0]=bus[x][i];
20 q[en][1]=1;
21 v[bus[x][i]]=true;
22 }
23 while (st<en){
24 ++st;
25 int nx=q[st][0];
26 int now=list[nx][1];
27 if (now==num){
28 deep=q[st][1];
29 enpos=nx;
30 break;
31 }
32 for (int i=1;i<=bus[now][0];++i) if (!v[bus[now][i]]){
33 ++en;
34 q[en][0]=bus[now][i];
35 q[en][1]=q[st][1]+1;
36 v[bus[now][i]]=true;
37 pre[q[en][0]]=q[st][0];
38 }
39 }
40 }
41
42 int main(){
43 scanf("%d",&n);
44 for (int i=1;i<=n;++i){
45 scanf("%d %d",&list[i][0],&list[i][1]);
46 bus[list[i][0]][++bus[list[i][0]][0]]=i;
47 }
48 scanf("%d %d %d",&num,&sa,&sb);
49 bfs(sa);
50 if (deep<ans){
51 ans=deep;
52 apos=enpos;
53 int x=apos;
54 alist[0]=0;
55 while (x>0){
56 alist[++alist[0]]=x;
57 x=pre[x];
58 }
59 }
60 for (int i=1;i<=n;++i) pre[i]=v[i]=false;
61 deep=OO;
62 bfs(sb);
63 if (deep<=ans){
64 ans=deep;
65 apos=enpos;
66 int x=apos;
67 alist[0]=0;
68 while (x>0){
69 alist[++alist[0]]=x;
70 x=pre[x];
71 }
72 }
73 if (ans==OO) printf("IMPOSSIBLE");
74 else{
75 printf("%d\n",ans);
76 for (int i=alist[0];i>0;--i) printf("%d\n",alist[i]);
77 }
78 }
79
posted on 2008-11-12 11:53
Joseph 阅读(300)
评论(0) 编辑 收藏 引用