题解 P3953 【逛公园】

· · 题解

最短路+记忆化搜索

最短路：

每一组数据的边数=点数*2，这是一个稀疏图

直接上spfa

问那些说会卡spfa的人两个问题：

1.NOIP有卡过spfa吗？（归程是NOI2018）

2.数据范围是明显的稀疏图，出题人的潜台词是什么？

记忆化搜索

我们用dfs(x,l)表示当前递归到x个点，现在还有l距离

转移方式：dfs(x,l)=dfs(y,d[x]+l-d[y]-z)

我用了动态数组+结构体存边，要存两次单向边 (这句话自己理解一下，不是存一次双向边）

如果检测到0环，就返回-1，否则返回方式数

别的

1.每步都要取余这种常识性的我就不讲了

2.多组数据要初始化

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll t,d[100001],f[100001][51],n,m,k,p;
bool working[100001][51];
struct node{
    ll to,edge;
    //to表示下一个点
    //edge表示长度
};
vector<node> head[100001],h[100001];
//head存正向边
//h存反向边

ll dfs(ll x,ll l){
    ll ans=0;
    if(l<0||l>k) return 0;//超出范围还没走到就返回
    if(working[x][l]){//找到0环
        working[x][l]=false;
        return -1;
    }
    if(f[x][l]!=-1) return f[x][l];//这个点已经走过了
    working[x][l]=true;
    for(ll i=0; i<h[x].size(); i++){
        ll y=h[x][i].to,z=h[x][i].edge,val=dfs(y,d[x]+l-d[y]-z);
        //y表示下一个格子
        //z表示剩下的距离
        if(val==-1){//找到0环
            working[x][l]=false;
            return -1;
        }
        ans=(ans+val)%p;
    }
    working[x][l]=false;//去过了
    if(x==1&&l==0) ans++;//找到，并且距离用完
    f[x][l]=ans;//存下结果
    return ans;
}

inline void spfa(){//最短路，不讲了
    memset(d,0x3f,sizeof(d));
    memset(f,-1,sizeof(f));
    queue<ll> q;
    q.push(1);
    d[1]=0;
    while(!q.empty()){
        ll x=q.front(); q.pop();
        for(ll i=0; i<head[x].size(); i++){
            ll y=head[x][i].to,z=head[x][i].edge;
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                q.push(y);
            }
        }
    }
}

ll work(){
    scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
    for(ll i=1; i<=n; i++){
        head[i].clear(); h[i].clear();
    }

    while(m--){
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        head[x].push_back(node{y,z});//存正边
        h[y].push_back(node{x,z});//存反边
    }
    spfa();
    ll ans=0;
    for(ll i=0; i<=k; i++){
        ll val=dfs(n,i);//调用
        if(val==-1) return -1;//找到0环直接退出
        ans=(ans+val)%p;//结果增加
    }
    return ans;
}

int main(){
    scanf("%lld",&t);
    while(t--) printf("%lld\n",work());
    return 0;
}