ABC137 E - Coins Respawn

問題

atcoder.jp

解法

• ゲーム開始からの経過時間をT分として T×P枚のコインの支払いが要求される→一回の移動で獲得できるコインの枚数をすべて-Pすればよい。
• 獲得できるコインの枚数を負にした値を移動コストと考えれば、最短経路問題となる。
• 頂点1からNまでを移動する経路の中に負の閉路があると、無限ループとなり最大値が求まらない。逆に言うと、それらの経路の外にあるような負の閉路は無視していい。 →DFSで頂点1, 頂点Nの両方ともから到達できない頂点は無視する。
• 負のコストを持つグラフの最短経路をベルマンフォード法で求める。

コード

template <class T>
void print(vector<vector<T>>& df) {
  for (auto& vec : df) {
    print(vec);
  }
}

struct edge {
  int from;
  int to;
  ll cost;
};

vector<edge> G[3000];
vi to[3000], rto[3000];
bool ok[2][3000];

void dfs(int u, int r) {
  if (ok[r][u]) return;
  ok[r][u] = true;
  if (r == 0) {
    for (auto v : to[u]) {
      dfs(v, r);
    }
  } else {
    for (auto v : rto[u]) {
      dfs(v, r);
    }
  }
}

int main() {
  int n, m, p;
  cin >> n >> m >> p;
  vl dist(n, (ll)1e10);
  rep(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    c -= p;
    edge e;
    e.to = b;
    e.cost = -c;
    G[a].push_back(e);
    to[a].push_back(b);
    rto[b].push_back(a);
  }

  dfs(0, 0);
  dfs(n - 1, 1);

  bool updated = true;
  int step = 0;
  dist[0] = 0;
  while (updated) {
    updated = false;
    rep(u, n) {
      for (auto e : G[u]) {
        int v = e.to;
        int cost = e.cost;
        if (!(ok[0][u] && ok[1][u])) continue;
        if (!(ok[0][v] && ok[1][v])) continue;
        int d = dist[u] + cost;
        if (dist[v] > d) {
          updated = true;
          dist[v] = d;
        }
      }
    }
    step++;
    if (step > n) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << max(0LL,-dist[n - 1]) << endl;
  return 0;
}