P3953 逛公园

· · 个人记录

首先可以想到，走到一个点时，只要长度是一定的，那么后面怎么走跟前面无关。这就是他和普通的最短路不同的原因。故可以考虑记忆化搜索

先求出最短路1到n的最短路d

怎么搜索呢？用f[i][k]表示走到点i后最终路线长度不超过d+k的方案数。在搜索时，比如我们走到一个点u，u到n的最短路是d_u；由u走到v时经过距离len，v到n的最短路是d_v。那么从u到n不超过k的路径可以从v处走，但是这可能会导致这多走路，多走的长度是delta=d_v+len-d_u，此时如果能求出f[v][k-delta]，他不就是f[u][k]的一部分吗？

这一波分析里可以看出还要先反向建图跑一遍预处理出每个点到n的最短路

AC代码

#include<bits/stdc++.h>
const int maxk=60;
const int maxn=100010;
const int maxm=200010;
using namespace std;

int T,n,m,k,p;
int tot,to[maxm],nxt[maxm],len[maxm],head[maxn];
int Rtot,Rto[maxm],Rnxt[maxm],Rlen[maxm],Rhead[maxn];
int dis[maxn],f[maxn][maxk];
bool vis[maxn],in[maxn][maxk];
priority_queue< pair<int,int> > Q;

inline void Add(int u,int v,int w) {to[++tot]=v,nxt[tot]=head[u],len[tot]=w,head[u]=tot;}
inline void RAdd(int u,int v,int w) {Rto[++Rtot]=v,Rnxt[Rtot]=Rhead[u],Rlen[Rtot]=w,Rhead[u]=Rtot;}

void init()
{
    tot=Rtot=0;
    memset(head,0,sizeof(head));
    memset(Rhead,0,sizeof(Rhead));
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(f,0,sizeof(f));
    memset(in,0,sizeof(in));
}

void RDijkstra()
{
    dis[n]=0;
    Q.push(make_pair(0,n));
    while(!Q.empty())
    {
        int u=Q.top().second;Q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=Rhead[u];i;i=Rnxt[i])
        {
            int v=Rto[i];
            if(dis[v]>dis[u]+Rlen[i])
            {
                dis[v]=dis[u]+Rlen[i];
                Q.push(make_pair(-dis[v],v));
            }
        }
    }
}

int dfs(int u,int K)
{
    if(in[u][K]) return -1;
    if(f[u][K]) return f[u][K];
    in[u][K]=1;
    if(u==n) f[u][K]=1;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        int dt=dis[v]+len[i]-dis[u];
        if(dt<=K)
        {
            int w=dfs(v,K-dt);
            if(w==-1) return -1;
            f[u][K]=(f[u][K]+w)%p;
        }
    }
    in[u][K]=0;
    return f[u][K];
}

int main()
{
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        init();
        scanf("%d%d%d%d",&n,&m,&k,&p);
        for(int i=1,u,v,w;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            Add(u,v,w);RAdd(v,u,w);
        }
        RDijkstra();
        printf("%d\n",dfs(1,k));
    }
    return 0;
}