Submission #6861421


Source Code Expand

Copy
#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

Submission Time
Task E - Coins Respawn
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2029 Byte
Status
Exec Time 47 ms
Memory 768 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03
All 500 / 500 a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46, b47, b48, b49, b50, b51, b52, b53, b54, b55, b56
after_contest 0 / 0 after_contest_57, after_contest_58, after_contest_59
Case Name Status Exec Time Memory
a01 1 ms 256 KB
a02 1 ms 256 KB
a03 1 ms 256 KB
after_contest_57 13 ms 768 KB
after_contest_58 13 ms 768 KB
after_contest_59 13 ms 768 KB
b04 1 ms 256 KB
b05 1 ms 256 KB
b06 1 ms 256 KB
b07 1 ms 256 KB
b08 1 ms 256 KB
b09 13 ms 768 KB
b10 13 ms 768 KB
b11 13 ms 768 KB
b12 10 ms 768 KB
b13 10 ms 768 KB
b14 13 ms 768 KB
b15 4 ms 512 KB
b16 4 ms 640 KB
b17 4 ms 640 KB
b18 13 ms 768 KB
b19 13 ms 768 KB
b20 13 ms 768 KB
b21 13 ms 768 KB
b22 9 ms 640 KB
b23 13 ms 768 KB
b24 9 ms 768 KB
b25 1 ms 384 KB
b26 21 ms 768 KB
b27 21 ms 768 KB
b28 21 ms 768 KB
b29 22 ms 768 KB
b30 22 ms 768 KB
b31 21 ms 768 KB
b32 22 ms 768 KB
b33 22 ms 768 KB
b34 23 ms 768 KB
b35 23 ms 768 KB
b36 24 ms 768 KB
b37 25 ms 768 KB
b38 21 ms 768 KB
b39 21 ms 768 KB
b40 21 ms 768 KB
b41 21 ms 768 KB
b42 21 ms 768 KB
b43 44 ms 768 KB
b44 44 ms 768 KB
b45 47 ms 768 KB
b46 45 ms 768 KB
b47 16 ms 768 KB
b48 11 ms 512 KB
b49 13 ms 768 KB
b50 14 ms 768 KB
b51 13 ms 768 KB
b52 14 ms 768 KB
b53 13 ms 768 KB
b54 20 ms 640 KB
b55 26 ms 768 KB
b56 32 ms 768 KB