HDU-1142-A Walk Through the Forest(Dijkstra+dfs)

#include <stdio.h>
#define INF 99999999

int d[1001],map[1001][1001],vis[1001],n;

int dfs(int x)//直接普通的dfs会超时，要把走过的点的结果保存下来
{
    if(x==2) return 1;//终点，返回1

    if(vis[x]) return vis[x];//如果已经走过，直接返回结果

    for(int i=2;i<=n;i++)//如果没走过，就dfs，并把结果保存下来再返回
    {
        if(map[x][i]<INF && d[x]>d[i])
        {
            vis[x]+=dfs(i);
        }
    }

    return vis[x];
}

int main()
{
    int m,i,j,a,b,c,minnum,minindex,t;

    while(~scanf("%d%d",&n,&m) && n)
    {
        for(i=1;i<=n;i++) d[i]=INF,vis[i]=0;
        for(i=1;i<=n;i++) for(j=1;j<=n;j++) map[i][j]=INF;

        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);

            if(map[a][b]>c) map[a][b]=map[b][a]=c;
        }
        
        
        //Dijkstra求出所有点到终点的最小距离
        d[2]=0;

        t=n-1;
        while(t--)
        {
            minnum=INF;
            for(i=1;i<=n;i++)
            {
                if(!vis[i] && d[i]<minnum)
                {
                    minnum=d[i];
                    minindex=i;
                }
            }

            vis[minindex]=1;

            for(i=1;i<=n;i++)
            {
                if(!vis[i] && d[i]>d[minindex]+map[minindex][i])
                {
                    d[i]=d[minindex]+map[minindex][i];
                }
            }
        }

        for(i=1;i<=n;i++) vis[i]=0;//这里用来保存dfs过程中每个点的结果

        printf("%d\n",dfs(1));
    }
}