题解：P3953 [NOIP2017 提高组] 逛公园

JayJessy · 2024-07-09 20:36:45 · 题解

难道有人看题解不点赞的吗？

题目解析

• 首先看到题目中写：“如果 1 号点 到 N 号点的最短路长为 d，那么策策只会喜欢长度不超过 d + K 的路线”。
  所以，很明显，我们要跑一遍 Dijkstra 算法。
• 接下来我们使用记忆化搜索。
  设 dp_{u,k} 为从 1 号点进去，从 u 号点出来，且花至多 dis_u+k 的时间，总共有多少条满足条件的路线。dp 初始值为 -1。dp_{1,k}=1。
• 遍历 u 的邻点 v，设 dp_{u,k} 由 dp_{v,k'} 转移得到，则 dis_u+k=dis_v+k'+w(u,v) k'=dis_u-dis_v+k-w(u,v)
• 不过还有个问题，就是什么时候输出 -1。
  发现这时会出现“零环”，所以我们要开一个 instk 数组，如果回溯前两次遍历到同一个状态便出现了“零环”。

呼，该讲的都讲完了，接下来是——

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PLL;
const ll N=1e5+10;
priority_queue<PLL,vector<PLL>,greater<PLL>> q;
vector<pair<ll,ll>> e[N],e2[N];
ll t,n,m,K,p,dis[N],dp[N][55];
bool flg,vis[N],instk[N][55];
ll dfs(ll u,ll k) {
    if(instk[u][k]==1) return -1;
    if(~dp[u][k]) return dp[u][k];
    instk[u][k]=1,dp[u][k]=(u==1);
    for(auto x:e2[u]) {
        ll v=x.first,w=x.second,nk=dis[u]-dis[v]+k-w;
        if(nk<0 || nk>K) continue;
        if(dfs(v,nk)==-1) return -1;
        dp[u][k]=(dp[u][k]+dp[v][nk])%p;
    }
    instk[u][k]=0;
    return dp[u][k];
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n>>m>>K>>p;
        for(ll i=1; i<=n; ++i) e[i].clear(),e2[i].clear();
        for(ll i=1,a,b,c; i<=m; ++i) cin>>a>>b>>c,e[a].push_back({b,c}),e2[b].push_back({a,c});
        for(ll i=1; i<=n; ++i) dis[i]=9e18,vis[i]=0;
        dis[1]=0,q=priority_queue<PLL,vector<PLL>,greater<PLL>>(),q.push({0,1});
        while(!q.empty()) {
            ll u=q.top().second;
            q.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(auto x:e[u]) {
                ll v=x.first,w=x.second;
                if(dis[v]>dis[u]+w) dis[v]=dis[u]+w,q.push({dis[v],v});
            }
        }
        for(ll i=1; i<=n; ++i) for(ll j=0; j<=K; ++j) dp[i][j]=-1,instk[i][j]=0;
        flg=0,cout<<dfs(n,K)<<"\n";
    }
    return 0;
}

完结撒花~~