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

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

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

第一眼紫题，便有了退缩之意，但这是必做题，于是我默默地点开了题解……然后就发现其实思路不是哪么难（代码调了两个小时）。

题目解析

• 首先看到题目中写：“如果 1 号点 到 N 号点的最短路长为 d，那么策策只会喜欢长度不超过 d + K 的路线”。
  所以，很明显，我们要跑一遍 Dijkstra 算法。

  void dij() {
  memset(vis1,0,sizeof(vis1));
  memset(d,0x3f,sizeof(d));
  d[1]=0;
  q.push({0,1});
  while(!q.empty()) {
      ll u=q.top().second;
      q.pop();
      if(vis1[u]) continue;
      vis1[u]=1;
      for(auto x:e1[u]) {
          ll v=x.first,w=x.second;
          if(d[v]>d[u]+w) d[v]=d[u]+w,q.push({d[v],v});
      }
  }
  }

• 接下来我们使用记忆化搜索。
  设 dp_{u,k} 为从 1 号点进去，从 u 号点出来，且花恰好 d[u]+k 的时间，总共有多少条满足条件的路线。dp 初始值为 -1。
  遍历 u 的邻点 v，设 dp_{u,k} 由 dp_{v,k'} 转移得到，则 d_u+k=d_v+k'+w(u,v) k'=d_u-d_v+k-w(u,v) 不过还有个问题，就是什么时候输出 $-1$。 发现这时会出现“零环”，所以我们要开一个 $vis$ 数组，如果两次遍历到同一个点便出现了“零环”。 ```cpp ll dfs(ll u,ll k) { if(vis2[u][k]) { flg=1; return 0; } if(~dp[u][k]) return dp[u][k]; vis2[u][k]=1; dp[u][k]=0; for(auto x:e2[u]) { ll v=x.first,w=x.second,nk=d[u]-d[v]+k-w; if(nk<0 || nk>K) continue; dp[u][k]=(dp[u][k]+dfs(v,nk))%p; if(flg) { vis2[u][k]=0; return 0; } } if(u==1 && k==0) dp[u][k]=1; vis2[u][k]=0; return dp[u][k]; } ``` 呼，该讲的都讲完了，接下来是—— ## AC 代码 ```cpp #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<PLL> e1[N],e2[N]; ll t,n,m,K,p,d[N],dp[N][60]; bool flg,vis1[N],vis2[N][60]; void dij() { memset(vis1,0,sizeof(vis1)); memset(d,0x3f,sizeof(d)); d[1]=0; q.push({0,1}); while(!q.empty()) { ll u=q.top().second; q.pop(); if(vis1[u]) continue; vis1[u]=1; for(auto x:e1[u]) { ll v=x.first,w=x.second; if(d[v]>d[u]+w) d[v]=d[u]+w,q.push({d[v],v}); } } } ll dfs(ll u,ll k) { if(vis2[u][k]) { flg=1; return 0; } if(~dp[u][k]) return dp[u][k]; vis2[u][k]=1; dp[u][k]=0; for(auto x:e2[u]) { ll v=x.first,w=x.second,nk=d[u]-d[v]+k-w; if(nk<0 || nk>K) continue; dp[u][k]=(dp[u][k]+dfs(v,nk))%p; if(flg) { vis2[u][k]=0; return 0; } } if(u==1 && k==0) dp[u][k]=1; vis2[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++) e1[i].clear(),e2[i].clear(); for(ll i=1,a,b,c; i<=m; i++) { cin>>a>>b>>c; e1[a].push_back({b,c}); e2[b].push_back({a,c}); } dij(); flg=0; memset(dp,-1,sizeof(dp)); ll ans=0; for(ll i=0; i<=K; i++) { ans=(ans+dfs(n,i))%p; if(flg) break; } if(flg) cout<<"-1\n"; else cout<<ans<<"\n"; } return 0; } ``` 完结撒花~~