hdu 1142 最短路+记忆化深搜---好题-白红宇

hdu 1142 最短路+记忆化深搜---好题

阅读量：5153 次

发布时间：2019-06-13

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

题意：他的办公室用1表示，家用2 表示，从1到2，中间可能会经过其它节点，而该节点可走的原则是：假设他此时在A处，B与其相邻，只有当B到2 路线中存在一条比A到2 的任意一条路径都短的路径，才能走B。问这样的路线有多少种？

分析：记忆化搜索不太会，这题难度就在这里。有挑战好玩。下面是大神的分析。欣赏下。

题目大意：寻找一共有多少条符合题意的路。能够从点A走到点B的要求是：点A到终点的最短路 > 点B到终点的最短路。也就是说：从终点出发，求每一个点的最短路，然后那些最短路的值记录起来，作为能否通过的判断条件。最后用记忆化搜索来搜索出一共多少条符合要求的路。普通的dfs是超时的，bfs是超内存的。

分析2：

做这题真可谓是一波三折，足足WA了有30&＃43;次。

1. 题目意思懂得错误。题目中的一段话没懂得好：

He considers taking a path A to B to be progress if there exists a route B to his home that is shorter than any possible route A.

这句话的意思是说，对于两点A，B，若是点B达到家里的最短路间隔小于点A达到家里的最短路间隔，那么点A就可以达到点B。

而我把这题懂得成了求有办公室到家里有几许条不合的最短路。

2. 解决了上述错误之后，接下来可以求出每一点达到点2（家里）的最短路，然后按照所求的各点最短路，求出有几许条到家里的路径。

若是直接搜刮是会超时的，所以要用记忆化搜刮。

3. 因为本身的粗心，因为我的法度中有两个数组名为d和dp，在写记忆话搜刮时把这两个数组混合了，成果又WA了十多次而找不到原因。

分析3：设定一个DP数组，DP[i] 表示第i点到点2有多少种符合条件的走法。然后用递归的方法从1点求出到2点的符合条件的走法。具体思想看代码。

View Code

// I'm lanjiangzhou//C#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            //C++#include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       #include 
                        
                         #include 
                         
                          #include 
                          
                           using namespace std;//*************************OUTPUT*************************#ifdef WIN32#define INT64 "%I64d"#define UINT64 "%I64u"#else#define INT64 "%lld"#define UINT64 "%llu"#endif//**************************CONSTANT***********************#define INF 0x3f3f3f3f// aply for the memory of the stack//#pragma comment (linker, "/STACK:1024000000,1024000000")//end#define maxn 1010int n,m;int edge[maxn][maxn];int S[maxn];int dis[maxn];int path[maxn];int dp[maxn];void dijkstra(int v0){ //初始化 for(int i=0;i
                           
                            dis[i]){ int t=dfs(i); sum+=t; } } dp[v]=sum; return sum; //返回：该点一共可以有多少条路}int main(){ int u,v,w; while(scanf("%d",&n)!=EOF){ if(n==0 ) break; scanf("%d",&m); //初始化 for(int i=0;i

转载于:https://www.cnblogs.com/lanjiangzhou/archive/2013/04/06/3002917.html

你可能感兴趣的文章