UVA 208 (DFS)

题意：找出1到T的所有路径；
坑点：一开始以为是到终点，读错了题意，没测试第二个样例，结果WA了4遍，坑大了；
 #include <iostream>

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <sstream>

 #include <algorithm>

 #define Max 2147483647

 #define INF 0x7fffffff

 #define N 90000+2

 #define M 40000

 #define ll long long

 #define mem(a,b) memset(a,b,sizeof(a))

 #define repu(i, a, b) for(int i = (a); i < (b); i++)

 #define repd(i, a, b) for(int i = (a-1); i >= (b); i--)

 const double PI=-acos(-1.0);

 using namespace std;

 const int maxn = ;

 int t = , v, sum, T;

 int rec[],vis[];

 int g[][] ,floyd[][];

 void dfs(int x,int n)

 {

     if(x==T)///到终点输出

     {

         printf("%d" ,);

         repu(i,,n-)

         printf(" %d",rec[i]);

         printf(" %d\n",T);

         sum++;

         return ;

     }

     repu(i,,v+)

     {

         if(!vis[i]&&g[x][i]==&&floyd[T][i]!=maxn)

         {///i点能到达终点+x,i通路+未访问过

             rec[n]=i;

             vis[i]=;

             dfs(i,n+);

             vis[i]=;

         }

     }

 }

 int main()

 {

     int x, y, cas = ;

     while (~scanf("%d", &T))

     {

         v = ;

         repu(i,,)

         repu(j,,)

         g[i][j] = floyd[i][j] = maxn;

         while(scanf("%d%d", &x, &y) && (x || y))

         {

             g[x][y] = g[y][x] = ;///无向图

             floyd[x][y] = floyd[y][x] = ;

             v = max(v,max(x,y));///找最大点

         }

         for(int k = ; k <= v; k++)///弗洛伊德算法找最短路，判断两点之间是否是通路

             for (int i = ; i <= v; i++)

                 for (int j = ; j <= v; j++)

                     floyd[i][j] = min(floyd[i][j],floyd[i][k] + floyd[k][j]);

         vis[] = ;

         sum = ;

         printf("CASE %d:\n", cas++);

         dfs(, );///从第一组数找起

         printf("There are %d routes from the firestation to streetcorner %d.\n", sum, T);

     }

     return ;

 }
DFS
相关文章
