結果
問題 | No.2366 登校 |
ユーザー |
![]() |
提出日時 | 2023-07-09 04:11:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 407 ms / 4,000 ms |
コード長 | 1,770 bytes |
コンパイル時間 | 2,355 ms |
コンパイル使用メモリ | 224,308 KB |
最終ジャッジ日時 | 2025-02-15 09:17:04 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;ll H, W, T;vector<vector<pair<ll, ll>>> field(80, vector<pair<ll, ll>>(80, {0, 0}));template<typename T> using pq = priority_queue<T, vector<T>, greater<T>>;void solve(){ll h, w, nh, nw, alt;ll x, t, c, d; //x...疲労度、t...時間pq<tuple<ll, ll, ll, ll>> que;int dx[4] = {1, 0, -1, 0};int dy[4] = {0, 1, 0, -1};vector<vector<vector<ll>>> dist(H, vector(W, vector<ll>(321, 9e18))); //-160~160vector<vector<vector<bool>>> visit(H, vector(W, vector<bool>(321)));dist[0][0][160] = 0;que.push({0, 0, 0, 160});while(!que.empty()){tie(x, h, w, t) = que.top();que.pop();if (visit[h][w][t]) continue;if (t == 320) continue;visit[h][w][t] = 1;for (int dir=0; dir < 4; dir++){nh = h + dx[dir];nw = w + dy[dir];if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;if (x < dist[nh][nw][t+1]){dist[nh][nw][t+1] = x;que.push({dist[nh][nw][t+1], nh, nw, t+1});}}if (field[h][w].first > 0){tie(c, d) = field[h][w];if (t-c >= 0 && x+d < dist[h][w][t-c]){dist[h][w][t-c] = x+d;que.push({dist[h][w][t-c], h, w, t-c});}}}ll mi=9e18;for (int i=0; i<=min(T+160, 320LL); i++){mi = min(mi, dist[H-1][W-1][i]);}cout << (mi == 9e18 ? -1 : mi) << endl;}int main(){ll K, a, b, c, d;cin >> H >> W >> K >> T;for (int i=0; i<K; i++){cin >> a >> b >> c >> d;a--; b--; c--;field[a][b] = {c, d};}solve();return 0;}