結果
問題 |
No.2712 Play more!
|
ユーザー |
|
提出日時 | 2024-11-01 20:18:02 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,454 bytes |
コンパイル時間 | 4,211 ms |
コンパイル使用メモリ | 324,860 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-01 20:18:31 |
合計ジャッジ時間 | 7,469 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 RE * 1 |
other | AC * 25 WA * 7 RE * 1 |
ソースコード
#include <bits/extc++.h> int main() { using namespace std; const auto find_shortest_path_cost{ [](const vector<tuple<unsigned, unsigned, long>> &edges, unsigned start, unsigned goal) -> optional<long> { const auto N{edges.size()}; constexpr auto inf{numeric_limits<long>::max()}; vector<long> distance(N, inf); distance[start] = 0; for (unsigned j{}; j + 1 < N; j++) for (const auto &[from, to, cost] : edges) if (distance[from] != inf && distance[to] > distance[from] + cost) distance[to] = distance[from] + cost; for (unsigned i{}; i < N; i++) for (const auto &[from, to, cost] : edges) if (distance[from] != inf && distance[to] > distance[from] + cost) distance[to] = -inf; if (distance[goal] == -inf) return nullopt; return distance[goal]; }}; unsigned N, M; cin >> N >> M; vector<long> A(N); for (auto &a : A) cin >> a; vector<tuple<unsigned, unsigned, long>> edges(M); for (auto &[a, b, c] : edges) { cin >> a >> b >> c; --a; --b; c = c - A[a]; } if (const auto ans{find_shortest_path_cost(edges, 0, N - 1)}; ans) cout << A.back() - *ans << endl; else cout << "inf" << endl; return 0; }