UVA 208 Firetruck （DFS+剪枝）-白红宇

UVA 208 Firetruck （DFS+剪枝）

阅读量：4916 次

发布时间：2019-06-11

本文共 699 字，大约阅读时间需要 2 分钟。

题意：构造出一张图，给出一个点，字典序输出所有从1到该点的路径

思路：这道题裸搜的话会超时，所以要进行必要的剪枝，刚开始我时用一个dfs从目标点开始搜，dfs能到达的点说明通过这个带你可以到达目标点，这样会超时，所以需要换另一种方法，这里我用的是flody，也可以用并查集。

代码：

#include #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define ll long long#define mod 1000000007#define mem(a) memset(a,0,sizeof(a))using namespace std;const int maxn = 20 + 5, inf = 0x3f3f3f3f;bool vis[maxn];int floyd[maxn][maxn];int d[maxn];bool G[maxn][maxn];int n,cnt,Maxn,len;void print(){ cnt++; cout<<1; for(int i = 1 ; i < len ; i ++ ){ cout<<" "<

转载于:https://www.cnblogs.com/seven7777777/p/10278741.html

你可能感兴趣的文章