Submission #6821415

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N = 2500 + 5;
int n, m, p;
vector < pair < int , int > > g[N], g2[N];
bool vis[N], vis2[N], instk[N];
vector < pair < int , int > > temp;
bool yes;
vector < pair < int, int >  > v;
bool check(int node){
  if (vis2[node])
    return 0;
  vis2[node] = 1;
  if (node == n)
    return 1;
  bool ret = 0;
  for(auto ch : g[node])
    ret |= check(ch.first);
  return ret;
}
bool reachable[N];
void dfs(int node){
  reachable[node] = 1;
  if (vis[node]){
    if (instk[node]){
    long long cost = 0;
    for(int i = v.size() -1  ; i >= 0 ; i--){
      cost += v[i].second - p;
      if (v[i].first == node)
        break;
    }
    if (cost > 0){
      memset(vis2,0,sizeof vis2);
      if (check(node))
        yes = 1;
    }
  }
    return;
  }
  instk[node] = 1;
  vis[node] = 1;
  for(auto ch : g[node]){
    v.push_back({node, ch.second});
    dfs(ch.first);
    v.pop_back();
  }
  instk[node] = 0;
}
int co[N];
long long topo(int node){
  if (!reachable[node])
    return -1e16;
  if (vis[node])
    return co[node];
  vis[node] = 1;
  long long ret = 0;
  for(auto ch : g2[node]){
    ret = max(ret, ch.second - p + topo(ch.first));
  }
  return co[node] = ret;
}
int main(){
  cin >> n >> m >> p;
  for(int i = 1 ; i <= m ; i++){
    int x, y, c;
    cin >> x >> y >> c;
    g[x].push_back({y, c});
    g2[y].push_back({x, c});
  }
  dfs(1);
  if (yes)
    return cout << -1,0;
  memset(vis,0,sizeof vis);
  long long ret = topo(n);
  cout << ret;
  return 0;
}

Submission Info

Judge Result