hdu 1142 A Walk Through the Forest（最短路+记忆化搜索）-CSDN博客

本文链接：https://blog.csdn.net/piaocoder/article/details/51058268

本文探讨了在给定n个点和m行联通关系及其距离的情况下，如何使用SPFA算法和记忆化搜索来计算从点1到点2之间，下一个点到点2的距离比当前点到点2的距离更短的路径数量。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

A Walk Through the Forest

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1142

解题思路：

给你n个点，m行关于这些点的联通关系，以及距离，求从1这个点到2这个点之间，下一个点到2这个点比当前点到2这个点的距离要

小的路径的条数。。。

AC代码：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

const int N = 1005;
int edge[N][N],dis[N],vis[N];
int cnt[N];
int n,m;

void spfa(int cur){
    memset(vis,0,sizeof(vis));
    for(int i = 1; i <= n; i++)
        dis[i] = INF;
    queue<int> q;
    dis[cur] = 0;
    vis[cur] = 1;
    q.push(cur);
    while(!q.empty()){
        cur = q.front();
        q.pop();
        vis[cur] = 0;
        for(int i = 1; i <= n; i++){
            if(dis[i] > dis[cur]+edge[cur][i]){
                dis[i] = dis[cur]+edge[cur][i];
                if(!vis[i]){
                    q.push(i);
                    vis[i] = 1;
                }
            }
        }
    }
}

int dfs(int cur){//记忆化搜索
    if(cnt[cur])
        return cnt[cur];
    if(cur == 2)
        return 1;
    for(int i = 1; i <= n; ++i){
        if(edge[cur][i] < INF && dis[cur] > dis[i]){
            cnt[cur] += dfs(i);
        }
    }
    return cnt[cur];
}

int main(){
    while(scanf("%d",&n),n){
        scanf("%d",&m);
        memset(cnt,0,sizeof(cnt));
        for(int i = 1; i <= n; ++i){
            edge[i][i] = 0;
            for(int j = i+1; j <= n; ++j){
                edge[i][j] = edge[j][i] = INF;
            }
        }
        int u,v,w;
        for(int i = 0; i < m; ++i){
            scanf("%d%d%d",&u,&v,&w);
            edge[u][v] = edge[v][u] = w;
        }
        spfa(2);
        printf("%d\n",dfs(1));
    }
    return 0;
}