[数据结构与算法]逛公园（洛谷P3953）

终于做出来了。。。。。。
题目
一位大佬的博客
然后按我的个人理解来说说思路吧。
首先建图，要建正向图和反向图。正向跑spfa，算出每个点到起点的最短距离，然后因为有的点可能没法在给定的条件下跑到终点，所以如果正向bfs会多做无用功，所以我们要反向bfs，从终点开始bfs。
然后就是松弛，因为你可以最多多走k个单位的冤枉路，所以对每条边，都要试一试，看看能不能多走冤枉路，多走的距离就是d[v]+u,v之间的距离(也就是e.dist)-d[u]
然后剩下的就是k-(d[v]+e.dist-d[u])
dfs(x,l)表示走到x点的时候，你还有l个单位的冤枉路可以走
然后就是零环问题，如果有条边权值为0，也就是说你可以在这条边上反复横跳(懂我意思吧），所以就有无穷个情况，所以要输出-1
代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> PII;
bool vis[maxn][51];
bool vis2[maxn];
ll d[maxn];
ll f[maxn][51];
ll n,m,k,p;
struct Edge
{
    int from,to,dist;
};

vector<Edge>edges;
vector<Edge>_edges;
vector<int>G[maxn];
vector<int>_G[maxn];

void add(int from,int to,int dist)
{
    edges.push_back({from,to,dist});
    int m=edges.size();
    G[from].push_back(m-1);
}

void _add(int from,int to,int dist)
{
    _edges.push_back({from,to,dist});
    int m=_edges.size();
    _G[from].push_back(m-1);
}

void init()
{
    memset(vis,false,sizeof(vis));
    memset(f,-1,sizeof(f));
    memset(d,inf,sizeof(d));
    for(int i=0;i<=n;i++)
    {
        G[i].clear();
        _G[i].clear();
    }
    edges.clear();
    _edges.clear();
}





void spfa()
{
    queue<ll>q;
    q.push(1);
    d[1]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<G[u].size();i++)
        {
            Edge e=edges[G[u][i]];
            int v=e.to;
            if(d[v]>d[u]+e.dist)
            {
                d[v]=d[u]+e.dist;
                q.push(v);

            }
        }
    }
}

ll dfs(int x,int l)
{
    ll ans=0;
    if(l<0||l>k)
        return 0;
    if(vis[x][l])
    {
        vis[x][l]=false;
        return -1;
    }
    if(f[x][l]!=-1)
        return f[x][l];
     vis[x][l]=true;
     for(int i=0;i<_G[x].size();i++)
     {
         Edge e=_edges[_G[x][i]];
         int v=e.to;
         ll val=dfs(v,l-(d[v]-d[x]+e.dist));
         if(val==-1)
         {
             vis[x][l]=false;
             return -1;
         }
         ans=(ans+val)%p;

     }
     vis[x][l]=false;
     if(x==1&&l==0)
        ans++;
     f[x][l]=ans;
     return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>k>>p;
        init();
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            cin>>u>>v>>w;
            add(u,v,w);
            _add(v,u,w);
        }
        spfa();
        ll ans=0;
        bool flag=true;
        for(int i=0;i<=k;i++)
        {
            ll val=dfs(n,i);
            if(val==-1)
                {
                    cout<<-1<<endl;
                    flag=false;
                    break;
                }
            ans=(ans+val)%p;
        }
        if(flag)
        cout<<ans<<endl;
    }
}

阅读世界，共赴山海

423全民读书节，邀你共读