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;
}