题目链接:
https://vjudge.net/problem/UVA-208
题意:
题解:
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 18 int k,vis[30],vis2[30],road[30],sum; 19 vector<int> G[maxn]; 20 21 bool bfs(){ 22 queue<int> q; 23 q.push(1); vis[1] = 1; 24 25 while(!q.empty()){ 26 int u = q.front(); q.pop(); 27 if(u == k) return true; 28 for(int i=0; i<(int)G[u].size(); i++){ 29 int v = G[u][i]; 30 if(!vis[v]) { 31 q.push(v); 32 vis[v] = 1; 33 } 34 } 35 } 36 return false; 37 } 38 39 void dfs(int cur,int u){ 40 road[cur] = u; 41 if(u == k){ 42 printf("%d", road[1]); 43 for(int i=2; i<=cur; i++) 44 printf(" %d", road[i]); 45 puts(""); 46 sum ++; 47 return ; 48 } 49 50 for(int i=0; i<(int)G[u].size(); i++){ 51 int v = G[u][i]; 52 if(!vis2[v]){ 53 vis2[v] = 1; 54 dfs(cur+1,v); 55 vis2[v] = 0; 56 } 57 } 58 } 59 60 int main(){ 61 int cas = 1; 62 while(scanf("%d",&k) == 1){ 63 MS(vis); MS(vis2); 64 for(int i=0; i<=20; i++) G[i].clear(); 65 sum = 0; 66 int u,v; 67 while(scanf("%d%d",&u,&v) && (u+v)){ 68 G[u].push_back(v); 69 G[v].push_back(u); 70 } 71 72 for(int i=0; i<=20; i++) 73 sort(G[i].begin(),G[i].end()); 74 75 printf("CASE %d: ",cas++); 76 vis2[1] = 1; 77 if(bfs()) dfs(1,1); 78 printf("There are %d routes from the firestation to streetcorner %d. ",sum,k); 79 } 80 81 return 0; 82 }