Submission #6861421

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

vector<bool> reacheable_s;
vector<bool> reacheable_e;
vector<bool> r;

void dfs(ll s, const vector<vector<ll>> &edges, vector<bool> &reacheable) {
  reacheable[s] = true;
  for (auto nxt: edges[s]) {
    if (!reacheable[nxt]) {
      dfs(nxt, edges, reacheable);
    }
  }
}

class BellmanFord {
 const ll INF = 1e18;
 struct edge { ll from, to, cost; };
 public:
  BellmanFord(ll n): n(n) {}
  void AddEdge(ll from, ll to, ll cost) {
    es.push_back(edge{from, to, cost});
  }
  vector<ll> ShortestPath(ll start) {
    vector<ll> d(n, INF);
    d[start] = 0;
    for (ll i=0; i<n; i++) {
      for (auto e: es) {
        if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
          d[e.to] = d[e.from] + e.cost;
          // printf("i=%d e.to = %d\n",i,e.to);
          if (i == n-1 && r[e.to])
            return vector<ll>();
        }
      }
    }
    return d;
  }
 private:
  ll n;
  vector<edge> es;
};

signed main() {
  ll N,M,P;
  cin>>N>>M>>P;
  BellmanFord bf(N);
  reacheable_s.resize(N, false);
  reacheable_e.resize(N, false);
  r.resize(N, false);
  vector<vector<ll>> edges_s(N);
  vector<vector<ll>> edges_e(N);

  rep(i,M){
    ll from, to, cost;
    cin >> from >> to >> cost;
    from--;
    to--;
    cost = -(cost -P);
    bf.AddEdge(from, to, cost);

    edges_s[from].push_back(to);
    edges_e[to].push_back(from);
  }

  // 0とN-1から到達可能な点rを求める
  dfs(0, edges_s, reacheable_s);
  dfs(N-1, edges_e, reacheable_e);
  rep(i,N){
    r[i] = reacheable_s[i] & reacheable_e[i];
    // printf("r[%d]=%x\n",i,r[i]);
  }

  auto d = bf.ShortestPath(0);
  if (d.size() == 0) {
    cout << -1 << endl;
    return 0;
  }
  cout << max((ll)0, -d[N-1])<< endl;
  return 0;
}

Submission Info

Judge Result