题解 P3953 【逛公园】

· · 题解

传送门

看到很多人找到〇环就退出，这样做是很不严谨的，因为要考虑可行路径会不会通过这个〇环

我选择的方法是先找出〇环（把边权为0的边拉出来跑 \text {tarjan}），然后判断〇环上的点 x 是否满足 dis[1][x]+dis[x][n] \leq dis[1][n]+k ，如果满足就说明可行的路径有可能通过这个〇环，就可以直接退出了

目前这份代码应该通过了我看到的所有 hack 数据，也通过了\text{UOJ} 的评测，应该不会有什么问题了

解决了〇环之后这题就简单多了，直接记忆化搜索就完事了，原理别的题解已经解释得很清楚了，此处不再赘述（毕竟我也是看他们的题解写出来的）

Talk \ is \ cheap.\ Show \ you \ the \ code. 
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,ljc,now,cnt,cnt2,cnt3,ans,tot,sum;
int head[maxn],head2[maxn],head3[maxn],dfn[maxn],low[maxn],dis[maxn],dis2[maxn],f[maxn][55];
bool ins[maxn],ling[maxn],flag;
inline int read(){
    int x=0; char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0' && c<='9') x=x*10+c-48, c=getchar();
    return x;
}
struct edge{
    int to,w,nxt;
} e[maxn*2],e2[maxn*2],e3[maxn*2];//e[]为正图的边，e2[]为反图的边，e3[]为边权为零的边（拿来跑tarjan） 
inline void add(int u,int v,int w){
    e[++cnt]=(edge) {v,w,head[u]};
    head[u]=cnt;
}
inline void add2(int u,int v,int w){
    e2[++cnt2]=(edge) {v,w,head2[u]};
    head2[u]=cnt2;
}
inline void add3(int u,int v,int w){
    e3[++cnt3]=(edge) {v,w,head3[u]};
    head3[u]=cnt3;
}
struct node{
    int num,dis;
    bool operator < (const node x) const {return dis>x.dis;}
} t;
priority_queue <node> q;
inline void dij(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0, q.push((node) {1,0});
    while(!q.empty()){
        t=q.top(), q.pop();
        int x=t.num;
        if(dis[x]!=t.dis) continue;
        for(int i=head[x],y;i;i=e[i].nxt){
            y=e[i].to;
            if(dis[x]+e[i].w<dis[y]) dis[y]=dis[x]+e[i].w, q.push((node) {y,dis[y]});
        }
    }
}
inline void dij2(){
    memset(dis2,0x3f,sizeof(dis2));
    dis2[n]=0, q.push((node) {n,0});
    while(!q.empty()){
        t=q.top(), q.pop();
        int x=t.num;
        if(dis2[x]!=t.dis) continue;
        for(int i=head2[x],y;i;i=e2[i].nxt){
            y=e2[i].to;
            if(dis2[x]+e2[i].w<dis2[y]) dis2[y]=dis2[x]+e2[i].w, q.push((node) {y,dis2[y]});
        }
    }
}
int dfs(int x,int k){//记忆化搜索 
    if(f[x][k]!=-1) return f[x][k];
    f[x][k]=0;
    for(int i=head2[x],y,t;i;i=e2[i].nxt){
        y=e2[i].to, t=dis[x]-dis[y]+k-e2[i].w;
        if(t<0) continue;
        f[x][k]=(f[x][k]+dfs(y,t))%ljc;//记得%%%ljc 
    }
    return f[x][k];
}
stack <int> s;
void tarjan(int x){
    dfn[x]=low[x]=++tot;
    ins[x]=1, s.push(x);
    for(int i=head3[x],y;i;i=e3[i].nxt){
        y=e3[i].to;
        if(!dfn[y]) tarjan(y), low[x]=min(low[x],low[y]);
        else if(ins[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        sum=0;
        do{
            now=s.top(), s.pop();
            ins[now]=0, ling[x]=1;
            sum++;
        } while(now!=x);
        if(sum==1) ling[x]=0;//记得加这句，因为在tarjan里面一个点也是环 
    }
}
int main(){
    int u,v,w,k,m,t;
    t=read();
    while(t--){
        n=read(), m=read(), k=read(), ljc=read();
        cnt=cnt2=cnt3=ans=flag=0;
        for(int i=1;i<=n;i++) head[i]=head2[i]=head3[i]=dfn[i]=low[i]=ins[i]=ling[i]=0;
        memset(e,0,sizeof(e));
        memset(e2,0,sizeof(e2));
        memset(e3,0,sizeof(e3));
        while(m--){
            u=read(), v=read(), w=read();
            add(u,v,w), add2(v,u,w);
            if(w==0) add3(u,v,w);//边权为0就加到e3[]中 
        }
        dij(), dij2();//正反两次dij 
        for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);//找出0环 
        for(int i=1;i<=n;i++) if(ling[i] && dis[i]+dis2[i]<=dis[n]+k) {flag=1; break;}
        if(flag) {printf("-1\n"); continue;}//如果有可行路径经过0环，直接输出-1 
        memset(f,-1,sizeof(f));
        f[1][0]=1;
        for(int i=0;i<=k;i++) ans=(ans+dfs(n,i))%ljc;//记得%%%ljc
        printf("%d\n",ans); 
    }
    return 0;
}