$NOIP2017$逛公园

\(NOIP2017\)逛公园

就口胡一下，懒得写了

记搜即可。

设\(f[pos][k]\)表示从\(n\)到\(pos\)的路径限制为\(k\)（含义为题面中的\(K\)）

建反图预处理出\(n\)到\(i\)的最短路\(Dis_i\)即可。

上面的\(k\)要满足\(Dis_v+w\leq k+Dis_u\)，化简后有：\(f[u][k]=∑f[v][k?(Dis_v?Dis_u+w)]\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int f=1,w=0;char x=0;
    while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
    while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
    return w*f;
}
const int K=60;
const int N=1e5+10;
const int M=2e5+10;
int n,m,k,p,num_edge,NUM_EDGE;
int head[M],Vis[N],Dis[N];
int Sead[M],Stk[N][K],f[N][K];
struct Edge{int next,to,dis;} edge[M],Sdge[M];
inline void Add(int from,int to,int dis)
{
    edge[++num_edge].next=head[from];
    edge[num_edge].dis=dis;
    edge[num_edge].to=to;
    head[from]=num_edge;
}
inline void Sdd(int from,int to,int dis)
{
    Sdge[++NUM_EDGE].next=Sead[from];
    Sdge[NUM_EDGE].dis=dis;
    Sdge[NUM_EDGE].to=to;
    Sead[from]=NUM_EDGE;
}
inline void Spfa()
{
    memset(Dis,0x3f,sizeof(Dis));
    queue<int> Q;Q.push(n);Vis[n]=1;Dis[n]=0;
    while(Q.size())
    {
        int x=Q.front();Q.pop(),Vis[x]=0;
        for(int i=Sead[x];i;i=Sdge[i].next)
            if(Dis[Sdge[i].to]>Dis[x]+Sdge[i].dis)
            {
                Dis[Sdge[i].to]=Dis[x]+Sdge[i].dis;
                if(!Vis[Sdge[i].to]) Q.push(Sdge[i].to),Vis[Sdge[i].to]=1;
            }
    }
}
inline int Dfs(int pos,int k)
{
    if(Stk[pos][k]) return -1;
    if(f[pos][k]) return f[pos][k];
    Stk[pos][k]=1,f[pos][k]=pos==n?1:0;
    for(int i=head[pos];i;i=edge[i].next)
    {
        int Now=k+Dis[pos]-Dis[edge[i].to]-edge[i].dis;
        if(Now<0) continue; int W=Dfs(edge[i].to,Now);
        if(W==-1) {f[pos][k]=-1;return -1;} f[pos][k]=(f[pos][k]%p+W%p+p)%p;
    }
    Stk[pos][k]=0;return f[pos][k];
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("A.in","r",stdin);
#endif
    int T=read();
    while(T--)
    {
        num_edge=NUM_EDGE=0;
        memset(f,0,sizeof(f));
        memset(Stk,0,sizeof(Stk));
        memset(head,0,sizeof(head));
        memset(Sead,0,sizeof(Sead));
        n=read(),m=read(),k=read(),p=read();
        for(int i=1,u,v,d;i<=m;i++)
            u=read(),v=read(),d=read(),Add(u,v,d),Sdd(v,u,d);
        Spfa();printf("%lld\n",Dfs(1,k));
    }
}

$NOIP2017$逛公园

原文：https://www.cnblogs.com/wo-shi-zhen-de-cai/p/11768316.html