結果
問題 |
No.2712 Play more!
|
ユーザー |
![]() |
提出日時 | 2024-04-30 11:18:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 179 ms / 2,000 ms |
コード長 | 1,711 bytes |
コンパイル時間 | 578 ms |
コンパイル使用メモリ | 65,372 KB |
最終ジャッジ日時 | 2025-02-21 09:52:16 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:67:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 67 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:69:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 69 | for (int i = 0; i < n; i++) scanf("%d", as + i); | ~~~~~^~~~~~~~~~~~~~ main.cpp:73:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 73 | scanf("%d%d%d", &a, &b, &c); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 2712.cc: No.2712 Play more! - yukicoder */ #include<cstdio> #include<vector> #include<queue> #include<algorithm> #include<utility> using namespace std; /* constant */ const int MAX_N = 2500; const long long LINF = 1LL << 62; /* typedef */ typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef vector<pii> vpii; /* global variables */ int as[MAX_N], es[MAX_N]; vpii nbrs[MAX_N], rnbrs[MAX_N]; ll ds[MAX_N], rds[MAX_N]; bool fs[MAX_N]; /* subroutines */ bool dijkstra(int n, int st, vpii nbrs[], ll ds[], bool lpf = false) { fill(es, es + n, 0); fill(ds, ds + n, LINF); ds[st] = 0; priority_queue<pli> q; q.push({0, st}); while (! q.empty()) { auto [ud, u] = q.top(); q.pop(); ud = -ud; if (ds[u] != ud || es[u] >= n) continue; if (lpf && u == st && ds[u] < 0) return true; for (auto [v, c]: nbrs[u]) { ll vd = ud + c - as[u]; int ve = es[u] + 1; if (ds[v] > vd || (ds[v] == vd && es[v] > ve)) { ds[v] = vd, es[v] = ve; q.push({-vd, v}); } } } return false; } /* main */ int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", as + i); for (int i = 0; i < m; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); a--, b--; nbrs[a].push_back({b, c}); rnbrs[b].push_back({a, c}); } dijkstra(n, 0, nbrs, ds); dijkstra(n, n - 1, rnbrs, rds); for (int u = 0; u < n; u++) fs[u] = (ds[u] < LINF && rds[u] < LINF); for (int u = 0; u < n; u++) if (fs[u] && dijkstra(n, u, nbrs, ds, true)) { puts("inf"); return 0; } dijkstra(n, 0, nbrs, ds); printf("%lld\n", -ds[n - 1] + as[n - 1]); return 0; }