HDU-1142-最短路+记忆化搜索

旧城等待， 2022-07-11 13:01 178阅读 0赞

# A Walk Through the Forest #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 8176    Accepted Submission(s): 3006**

Problem Description

Jimmy experiences a lot of stress at work these days, especially since his accident made working difficult. To relax after a hard day, he likes to walk home. To make things even nicer, his office is on one side of a forest, and his house is on the other. A nice walk through the forest, seeing the birds and chipmunks is quite enjoyable.   
The forest is beautiful, and Jimmy wants to take a different route everyday. He also wants to get home before dark, so he always takes a path to make progress towards his house. He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A. Calculate how many different routes through the forest Jimmy might take.

Input

Input contains several test cases followed by a line containing 0. Jimmy has numbered each intersection or joining of paths starting with 1. His office is numbered 1, and his house is numbered 2. The first line of each test case gives the number of intersections N, 1 < N ≤ 1000, and the number of paths M. The following M lines each contain a pair of intersections a b and an integer distance 1 ≤ d ≤ 1000000 indicating a path of length d between intersection a and a different intersection b. Jimmy may walk a path any direction he chooses. There is at most one path between any pair of intersections.

Output

For each test case, output a single integer indicating the number of different routes through the forest. You may assume that this number does not exceed 2147483647

Sample Input

5 6
    1 3 2
    1 4 2
    3 4 3
    1 5 12
    4 2 34
    5 2 24
    7 8
    1 3 1
    1 4 1
    3 7 1
    7 4 1
    7 5 1
    6 7 1
    5 2 1
    6 2 1
    0

Sample Output

2
    4

**题目大意：**

给你n个点和m条边（无向图）问你从1到2的路径的个数，定义从A到B

当且仅当存在B到2的路径要与短于所有从A到2的路径

**题目思路：**

根据我们知道A到B可走的条件是dis\[B\]<dis\[A\]（dis\[i\]为i到2的最短时间）

所以我们可以先跑一边最短路求出所有点到2的最短时间，

这里可以反向跑一边，以2为起点，因为是无向图，所以

就相当求出了其他点到达2的最短时间，然后我们可以从1开始dfs

与x相连的点当中只有当dis\[i\]<dis\[x\]才能走，当x走过时直接返回它的值

当x为2时返回1表示一条可行路径

**AC代码：**

#include<cstdio>
    
    const int maxn = 1e3+10;
    const int inf = 1e8;
    
    class dfsDij{
    public:
    
        int n,m;
        int mp[maxn][maxn],dis[maxn],dp[maxn],vis[maxn];
    
        int dfs(int x){
            if(dp[x]!=-1)return dp[x];         //当前点已经走过了
            if(x==2)return 1;                  //存在一条可行的路径
            int sum(0);
            for(int i=1;i<=n;i++){
                if(mp[x][i]<inf&&dis[i]<dis[x]&&i!=x){
                    sum+=dfs(i);
                }
            }
            return dp[x]=sum;
        }
    
        void dij(){
            for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0;
            dis[2]=0,vis[2]=1;
            for(int i=1;i<=n;i++){
                int to = 2,v=inf;
                for(int j=1;j<=n;j++)
                    if(!vis[j]&&dis[j]<v){
                        v=dis[j];
                        to=j;
                    }
                vis[to]=1;
                for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]>dis[to]+mp[to][j])
                    dis[j]=dis[to]+mp[to][j];
            }
        }
    
        void init(){
            while(scanf("%d",&n),n){
                scanf("%d",&m);
                for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)mp[i][j]=inf,dp[j]=-1;
                while(m--){
                    int u,v,w;scanf("%d%d%d",&u,&v,&w);
                    mp[u][v]=mp[v][u]=w;
                }
                dij();
                printf("%d\n",dfs(1));
            }
        }
    
    }dd;
    
    int main()
    {
        dd.init();
        return 0;
    }