|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#include <iostream> #include <string.h> #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int mat[25][25]; int dist[25][25]; vector<int> vb[25]; bool visit[25]; int fire; int kase=1; int mx=0,cnt=0; int res[25]; void dfs(int s,int k) { if(s==fire) { cnt++; for(int i=0;i<k;i++) { cout<<res[i]<<(i==(k-1)?"\n":" "); } return; } //for(int i=0;i<vb[s].size();i++) for(int i=1;i<=mx;i++) { if(visit[i]) continue; if(!mat[s][i]) continue; if(!dist[i][fire]) continue; visit[i]=1; res[k] = i; dfs(i,k+1); visit[i]=0; //int d = vb[s][i]; //if(dist[s][d]==0)// //continue; //if(visit[d]==0) //{ //visit[d]=1; //res[k]=d; //dfs(d,k+1); //visit[d]=0; //} } } void floyd() { for(int i=1;i<=mx;i++) { for(int j=1;j<=mx;j++) { for(int k=1;k<=mx;k++) { if(dist[j][i]==1 && dist[i][k]==1) dist[j][k] = 1; } } } } int main() { int a,b,k; for(int i=0;i<25;i++) { res[i] = 0; } while(scanf("%d",&fire)!=EOF)//cin>>fire { mx=0; memset(mat,0,sizeof(mat)); memset(dist,0,sizeof(dist)); while(cin>>a) { cin>>b; if(a==0 && b==0) { break; } dist[a][b]=1; dist[b][a]=1; mat[a][b]=1; mat[b][a]=1; //vb[a].push_back(b); //vb[b].push_back(a); mx = max(mx,max(a,b)); } cnt=0; /*if(fire==1) { cout<<"There are "<<0<<" routes from the firestation to streetcorner "<<fire<<".\n"; }*/ //else memset(visit,0,sizeof(visit)); visit[1]=1; k=0; res[k]=1; k+=1; floyd(); //for(int i=1; i<=mx; i++) //sort(vb[i].begin(), vb[i].end()); cout<<"CASE "<<kase++<<":\n"; dfs(1,k); cout<<"There are "<<cnt<<" routes from the firestation to streetcorner "<<fire<<".\n"; } return 0; } |