逛公园

题意：
有一个n个节点，m条有向边的图，如果从1到n的最短路为d，请你求从1到n的路线长度小于d+k的数目，答案对p取模。

思路：
最短路+记忆化搜索
反向建图求每一个节点到n节点的最短距离。
定义状态dp[i][j]为从节点i，还可以额外多走j的长度的状态到目标状态( dp[n][ji] (k>=ji>=0) )的路线数目.
如何判断在到目标状态过程中有零环：如果他从dp[i][j]状态又回到了dp[i][j]状态则说明存在零环，此时就会有无数条路线。

代码：

#include<bits/stdc++.h>

#define ll long long
#define eps 1e-8

using namespace std;

const ll inf=1e9+7;

int n, m, ki, mod;

struct w
{
    int to, cast;
} w;

vector<struct w> g[100005], fg[100005];

struct p
{
    int v, cast;
} p, p2;

bool operator<(struct p a,struct p b)
{
    return a.cast>b.cast;
}

int d[100005];

void djk()
{
    fill(d,d+100005,inf);
    d[n]=0;
    p.v=n;
    p.cast=0;
    priority_queue<struct p> q;
    q.push(p);
    while(!q.empty())
    {
        p=q.top();
        q.pop();
        int v=p.v, t=p.cast;
        if(t>d[v])
        {
            continue;
        }
        for(int i=0; i<fg[v].size(); i++)
        {
            int u=fg[v][i].to, cast=fg[v][i].cast;
            if(d[u]>t+cast)
            {
                d[u]=t+cast;
                p2.v=u;
                p2.cast=d[u];
                q.push(p2);
            }
        }
    }
}

int dp[100005][55], flag[100005][55];

int dfs(int v,int k)
{
    if(flag[v][k])
    {
        return dp[v][k]=-1;
    }
    if(dp[v][k])
    {
        return dp[v][k];
    }
    if(v==n)
    {
        dp[v][k]=1;
    }
    flag[v][k]=1;
    for(int i=0;i<g[v].size();i++)
    {
        int u=g[v][i].to, t=g[v][i].cast;
        if(t-(d[v]-d[u])<=k)
        {
            int pi=dfs(u,k-(t-(d[v]-d[u])));
            if(pi==-1)
            {
                return dp[v][k]=-1;
            }
            dp[v][k]=(dp[v][k]+dp[u][k-(t-(d[v]-d[u]))])%mod;
        }
    }
    flag[v][k]=0;
    return dp[v][k];
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&m,&ki,&mod);
        memset(flag,0,sizeof(flag));
        for(int i=0; i<m; i++)
        {
            int u, v, t;
            scanf("%d%d%d",&u,&v,&t);
            w.to=v;
            w.cast=t;
            g[u].push_back(w);
            w.to=u;
            fg[v].push_back(w);
        }
        djk();
        memset(dp,0,sizeof(dp));
        cout << dfs(1,ki) << endl;
        for(int i=1; i<=n; i++)
        {
            g[i].clear();
            fg[i].clear();
        }
    }
    return 0;
}