結果
問題 | No.2712 Play more! |
ユーザー |
|
提出日時 | 2024-03-31 15:17:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 2,409 bytes |
コンパイル時間 | 1,802 ms |
コンパイル使用メモリ | 198,392 KB |
最終ジャッジ日時 | 2025-02-20 17:48:46 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using ll = long long; constexpr ll INF = (1LL << 61); // 辺 struct Edge { int from; int to; ll cost; }; // ベルマンフォード法 (1.2 負閉路の影響を受ける頂点を調べる) // 負の閉路が存在する場合 true を返し, 負閉路の影響を受ける頂点は -INF にセットされる // distances は頂点数と同じサイズ, 全要素 INF で初期化しておく bool BellmanFord(const std::vector<Edge>& edges, std::vector<long long>& distances, int startIndex) { distances[startIndex] = 0; for (size_t i = 0; i < distances.size(); ++i) { bool changed = false; // 各辺について for (const auto& edge : edges) { // (INF + cost) は INF なので処理しない if (distances[edge.from] == INF) { continue; } // to までの新しい距離 const long long d = (distances[edge.from] + edge.cost); // d が現在の記録より小さければ更新 if (d < distances[edge.to]) { distances[edge.to] = d; changed = true; } } // どの頂点も更新されなかったら終了 if (!changed) { return false; } } // 頂点数分だけさらに繰り返し, 負閉路の影響を受ける頂点に -INF を伝播 for (size_t i = 0; i < distances.size(); ++i) { for (const auto& edge : edges) { if (distances[edge.from] == INF) { continue; } const long long d = (distances[edge.from] + edge.cost); if (d < distances[edge.to]) { // 負閉路の影響を受ける頂点を -INF に distances[edge.to] = -INF; } } } return true; } int main() { ll N, M; std::cin >> N >> M; std::vector<ll> A(N); for (ll& a : A) std::cin >> a; std::vector<Edge> edges; for (int i = 0; i < M; i++) { int a, b; ll c; std::cin >> a >> b >> c; edges.push_back(Edge{a - 1, b - 1, c - A[b - 1]}); } std::vector<ll> distances(N, INF); BellmanFord(edges, distances, 0); if (distances[N - 1] == -INF) { std::cout << "inf" << std::endl; } else { std::cout << A[0] - distances[N - 1] << std::endl; } }