結果
問題 |
No.1545 [Cherry 2nd Tune N] Anthem
|
ユーザー |
![]() |
提出日時 | 2021-06-12 21:40:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 514 ms / 3,000 ms |
コード長 | 2,404 bytes |
コンパイル時間 | 1,278 ms |
コンパイル使用メモリ | 118,152 KB |
実行使用メモリ | 39,548 KB |
最終ジャッジ日時 | 2024-12-17 19:16:33 |
合計ジャッジ時間 | 16,502 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 67 |
ソースコード
/* -*- coding: utf-8 -*- * * 1545.cc: No.1545 [Cherry 2nd Tune N] Anthem - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 100000; const int MAX_K = 30000; /* typedef */ typedef unsigned int ui; typedef vector<ui> vu; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ui> plu; typedef vector<pii> vpii; typedef map<ui,ll> mul; typedef map<ui,ui> muu; /* global variables */ int xs[MAX_N]; vpii nbrs[MAX_N]; mul ds; muu ps; /* subroutines */ inline ui ab2p(ui a, ui b, int k) { return a * k + b; } inline void p2ab(ui p, ui &a, ui &b, int k) { a = p / k, b = p % k; } /* main */ int main() { int n, st, gl, k; scanf("%d%d%d%d", &n, &st, &gl, &k); st--, gl--; for (int i = 0; i < n; i++) scanf("%d", xs + i); int m; scanf("%d", &m); for (int i = 0; i < m; i++) { int a, b, y; scanf("%d%d%d", &a, &b, &y); a--, b--; nbrs[a].push_back(pii(b, y)); } ui stp = ab2p(st, 0, k), glp = ab2p(gl, k - 1, k); ds[stp] = xs[st]; priority_queue<plu> q; q.push(plu(-xs[st], stp)); while (! q.empty()) { plu u = q.top(); q.pop(); ll ud = -u.first; ui up = u.second; if (ds[up] != ud) continue; if (up == glp) break; ui ua, ub; p2ab(up, ua, ub, k); for (auto vy: nbrs[ua]) { ui va = vy.first, vb = min<ui>(ub + 1, k - 1); ui vp = ab2p(va, vb, k); ll vd = ud + vy.second + xs[va]; mul::iterator mit = ds.find(vp); if (mit == ds.end()) { ds[vp] = vd; ps[vp] = up; q.push(plu(-vd, vp)); } else if (mit->second > vd) { mit->second = vd; ps[vp] = up; q.push(plu(-vd, vp)); } } } mul::iterator mit = ds.find(glp); if (mit == ds.end()) puts("Impossible"); else { vu vs; vs.push_back(gl); for (muu::iterator mit0 = ps.find(glp); mit0 != ps.end();) { vs.push_back(mit0->second / k); mit0 = ps.find(mit0->second); } printf("Possible\n%lld\n%lu\n", mit->second, vs.size()); for (int i = vs.size() - 1; i >= 0; i--) printf("%u%c", vs[i] + 1, (i > 0) ? ' ' : '\n'); } return 0; }