学步园

这题刚开始思考了半天却没想到什么好的办法，最后看了解题报告，发现我从一开始就没有记忆化搜索这方面的想法，我想到了求出每个点到终点的最短路，却没想到用记忆花搜索来解决路径条数

思路：最短路+记忆化搜索

code：

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3fffffff;
int n,m;

int adj[1005],ec;
struct edge{
    int to,next,w;
}p[500001];
void add(int from,int to,int w)
{
    p[ec].to=to;
    p[ec].w=w;
    p[ec].next=adj[from];
    adj[from]=ec++;
}

int dis[1005];
bool inq[1005];
void spfa(int s)
{
    int i,to,w;
    queue<int> q;
    dis[s]=0;
    q.push(s);
    inq[s]=true;
    while(!q.empty())
    {
        s=q.front();
        q.pop();

        inq[s]=false;

        for(i=adj[s];i;i=p[i].next)
        {
            w=p[i].w;
            to=p[i].to;
            if(dis[to] > dis[s]+w)
            {
                dis[to]=dis[s]+w;
                if(!inq[to])
                {
                    inq[to]=true;
                    q.push(to);
                }
            }
        }

    }
}

int dp[1005];
int dfs(int from)
{
    int i,to,sum=0;
    if(dp[from])
    {
        return dp[from];
    }
    if(from==2)
    {
        return 1;
    }

    for(i=adj[from];i;i=p[i].next)
    {
        to=p[i].to;
        if(dis[to] < dis[from])
        {
            sum+=dfs(to);
        }
    }

    dp[from]=sum;
    return sum;
}

void init()
{
    int i;
    ec=1;
    for(i=1;i<=n;i++)
    {
        dis[i]=INF;
    }
    memset(dp,0,sizeof(dp));
    memset(adj,0,sizeof(adj));
    memset(inq,false,sizeof(inq));
}

int main()
{
    int i,a,b,w;
    while(~scanf("%d",&n) && n)
    {
        scanf("%d",&m);
        init();

        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&w);
            add(a,b,w);
            add(b,a,w);
        }

        spfa(2);

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