結果
問題 |
No.2366 登校
|
ユーザー |
|
提出日時 | 2024-05-02 00:58:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,968 bytes |
コンパイル時間 | 2,130 ms |
コンパイル使用メモリ | 186,908 KB |
実行使用メモリ | 12,508 KB |
最終ジャッジ日時 | 2024-11-22 09:56:55 |
合計ジャッジ時間 | 4,113 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 WA * 9 |
ソースコード
// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int h, w, k, t;cin >> h >> w >> k >> t; if(t >= h + w - 2){ cout << 0 << endl; return 0; } vector<vector<ll>> C(h, vector<ll>(w)), D(h, vector<ll>(w)); for(int i = 0; i < k; i++){ int y, x, v1, v2; cin >> y >> x >> v1 >> v2; y--, x--; C[y][x] = v1; D[y][x] = v2; } int temp = h + w - 2 - t; const ll INF = 1ll << 20; vector<vector<vector<ll>>> v(temp, vector<vector<ll>>(h, vector<ll>(w, INF))); priority_queue<tuple<ll, ll, int, int>> pq; v[0][0][0] = 0; pq.emplace(0, 0, 0, 0); ll ans = INF; while(!pq.empty()){ ll tim, d; int y, x; tie(d, tim, y, x) = pq.top(); pq.pop(); if(d > v[tim][y][x]) continue; if(C[y][x] >= 2){ ll nt = tim + C[y][x] - 1; if(nt < temp){ if(d + D[y][x] < v[nt][y][x]){ v[nt][y][x] = d + D[y][x]; pq.emplace(v[nt][y][x], nt, y, x); } } else{ ans = min(ans, d + D[y][x]); } } for(int i = 0 ; i < 4 ; i++){ int yy = y + (i == 0) - (i == 1); int xx = x + (i == 2) - (i == 3); if(yy < 0 || xx < 0 || yy >= h || xx >= w) continue; if(yy < y || xx < x){ ll nt = tim - 2; if(nt < 0) continue; if(d >= v[nt][yy][xx]) continue; v[nt][yy][xx] = d; pq.emplace(d, nt, yy, xx); }else{ if(d >= v[tim][yy][xx]) continue; v[tim][yy][xx] = d; pq.emplace(d, tim, yy, xx); } } } if(ans == INF) ans = -1; cout << ans << endl; }