題意：給出一個n個節點的無向圖，以及某個節點k，按照字典序從小到大輸出從節點1到節點k的所有路徑

看的題解

http://blog.csdn.net/hcbbt/article/details/9755147

因為節點數很少（小于20），所以可以先用floyd處理一下，判斷一點是否能夠到達終點

然后就像紫書里面枚舉排列那樣的去挨個找出字典序從小到大的路徑

題解里面說到的無回溯的走遍和終點相連的所有點，他寫的代碼是判斷的d[en][i],判斷終點到i點是否可達

寫成d[i][en]也能過，因為是無向圖

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 14 15 typedef long long LL; 16 const int INF = (1<<30)-1; 17 const int mod=1000000007; 18 const int maxn=55; 19 20 int d[maxn][maxn],rute[maxn],vis[maxn]; 21 int en,n,ans; 22 23 void dfs(int x,int cnt){ 24 if(x==en){ 25 printf("1"); 26 for(int i=1;i<cnt-1;i++) printf(" %d",rute[i]); 27 printf(" %d\n",en); 28 ans++; 29 return; 30 } 31 32 for(int i=2;i<=n;i++){ 33 if(!vis[i]&&d[x][i]==1&&d[i][en]!=INF){ 34 rute[cnt]=i; 35 vis[i]=1; 36 dfs(i,cnt+1); 37 vis[i]=0; 38 } 39 } 40 } 41 42 43 int main(){ 44 int kase=0; 45 while(scanf("%d",&en)!=EOF){ 46 int u,v; 47 n=-1; 48 for(int i=1;i<=55;i++){ 49 for(int j=1;j<=55;j++) { 50 d[i][j]=INF; 51 } 52 } 53 54 while(scanf("%d %d",&u,&v)&&(u||v)){ 55 d[u][v]=d[v][u]=1; 56 n=max(max(u,v),n);//找出這張圖里面最大的點的標號 57 } 58 59 for(int k=1;k<=n;k++) 60 for(int i=1;i<=n;i++) 61 for(int j=1;j<=n;j++) 62 d[i][j]=min(d[i][j],d[i][k]+d[k][j]); 63 64 ans=0; 65 memset(vis,0,sizeof(vis)); 66 67 printf("CASE %d:\n", ++kase); 68 dfs(1,1); 69 printf("There are %d routes from the firestation to streetcorner %d.\n", ans, en); 70 } 71 return 0; 72 } View Code

?

?

?

?

?

?

?

?

?

?

?

?

?

不知道是不是真的理解了的說啊-----

加油啊---g00000000000

轉載于:https://www.cnblogs.com/wuyuewoniu/p/4480098.html

總結

以上是生活随笔為你收集整理的UVa 208 Firetruck【回溯】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。