hdu1142 A Walk Through the Forest

#include<stdio.h>

const int MAX=1005;
const int INF=2000000000;
int g[MAX][MAX],dis[MAX];
bool visit[MAX];
int dp[MAX];            //dp[i]记录点i到家的路线的个数

int n;

void initial()
{
    for(int i=1;i<=n;i++)
    {
        visit[i]=0;
        dp[i]=-1;        //记忆结果初始化

    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            g[i][j]=INF;
}

void dijkstra(int start)
{
    for(int i=1;i<=n;i++)
        dis[i]=g[2][i];
    dis[2]=0;
    visit[2]=1;

    for(int i=1;i<n;i++)
    {
        int min=INF,v=-1;
        for(int j=1;j<=n;j++)
        {
            if(!visit[j]&&min>dis[j])
            {
                v=j;
                min=dis[j];
            }
        }

        if(v==-1) return;    //若为连通图则不需要该判断

        visit[v]=1;
        for(int j=1;j<=n;j++)
        {
            if(!visit[j]&&dis[j]>dis[v]+g[v][j])
            {
                dis[j]=dis[v]+g[v][j];
            }
        }
    }
}

int dfs(int depth)
{
    if(dp[depth]!=-1) return dp[depth];        //注意与普通dfs的区别

    
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(g[depth][i]!=INF&&dis[depth]>dis[i])        
        {
            int cur=dfs(i);
            sum+=cur; //累计路径的个数

        }
    }
    dp[depth]=sum;            
    return sum;
}

int main()
{
    while(scanf("%d",&n),n)
    {
        initial();

        int m;
        scanf("%d",&m);
        int v1,v2,c;
        while(m--)
        {
            scanf("%d%d%d",&v1,&v2,&c);
            if(c<g[v1][v2])    g[v1][v2]=g[v2][v1]=c; //去重边

        }

        dijkstra(2);

        dp[2]=1;
        printf("%d\n",dfs(1));
    }
    return 0;
}

总结:

题意大致是找总共有多少条从办公室到家的路径，这条路径满足先前的点到家的最短路径大于后来的点到家的最短路径。首先用dijkstra算法预处理得到每个点到家的最短路径，而后从办公室开始搜索到家的路径的条数，由于存在重复的搜索，因而将每次搜索的结果记录下来，当下次需要重复搜索该位置时可以直接读取结果而不必再次一直搜索到家。