题解：AT_abc137_e [ABC137E] Coins Respawn

DragonForge · 2025-03-08 11:55:05 · 题解

题解：AT_abc137_e [ABC137E] Coins Respawn

这是一道非常经典的求“正环”的题。由于走过每条边都需要 1 分钟，而平均每分钟都需要支付 P 枚金币，那么走过这条边真正能获得的金币数是边权减去 P。这样下来，题目就可以理解为：从 1 走到 n，输出可以得到金币的最大值。若金币数是负数或是无穷大，那么输出 -1。为了与判负环模板照应，我将做完差的边权值取相反数，最后输出就只需要再取相反数就行。

code

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAXN=2510,inf=1e18;

int n,m,p,dis[MAXN],vis[MAXN],h[MAXN],cnt[MAXN],visd[MAXN];
vector<pair<int,int>> e[MAXN];
vector<int> vec[MAXN];

inline void dfs(int u){
    if(visd[u]) return;
    visd[u]=1;
    for(auto v:vec[u]){
        dfs(v);
    }
}

inline bool spfa(){
  queue<int> q;
  fill(dis+2,dis+1+n,-inf);
  vis[1]=1;
  q.push(1);
  while(!q.empty()){
    int u=q.front();
    q.pop();
    vis[u]=0;
    for(auto [v,w]:e[u]){
        if(!visd[v]) continue;
      if(dis[v]<dis[u]+w){
        dis[v]=dis[u]+w;
        if(!vis[v]){
          vis[v]=1;
                q.push(v);
          cnt[v]=cnt[u]+1;
                if(cnt[v]>=n){
                  return 1;
          }
        }
      }
    }
  }
  return 0;
}

signed main(){
  cin>>n>>m>>p;
  for(int i=1,u,v,w;i<=m;i++){
    cin>>u>>v>>w;
    e[u].push_back({v,w-p});
    vec[v].emplace_back(u);
  }
  dfs(n);
  if(spfa()) cout<<"-1";
  else cout<<max(0LL,dis[n]);
  return 0;
}