結果
問題 | No.1638 Robot Maze |
ユーザー |
|
提出日時 | 2021-08-06 21:53:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,494 bytes |
コンパイル時間 | 1,500 ms |
コンパイル使用メモリ | 177,644 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-17 01:49:14 |
合計ジャッジ時間 | 2,761 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 27 | auto [c, now] = q.top(); | ^
ソースコード
#include <bits/stdc++.h> using namespace std; typedef pair<long long, long long> Pa; int main(){ int H, W; cin >> H >> W; int U, D, R, L; cin >> U >> D >> R >> L; long long K, P; cin >> K >> P; int xs, ys, xt, yt; cin >> xs >> ys >> xt >> yt; xs--; xt--; ys--; yt--; vector<string> S(H); for(int i = 0; i < H; i++) cin >> S[i]; long long INF = 1000000000000000000; vector<long long> cost(H * W, INF); priority_queue<Pa, vector<Pa>, greater<Pa>> q; int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0}; long long T[4] = {R, U, L, D}; cost[xs * W + ys] = 0; q.push({cost[xs * W + ys], xs * W + ys}); while(!q.empty()){ auto [c, now] = q.top(); q.pop(); if(cost[now] < c) continue; int x = now / W, y = now % W; for(int i = 0; i < 4; i++){ int nx = x + dx[i], ny = y + dy[i]; if(0 <= nx && nx < H && 0 <= ny && ny < W){ if(S[nx][ny] == '.' && cost[nx * W + ny] > c + T[i]){ cost[nx * W + ny] = c + T[i]; q.push({cost[nx * W + ny], nx * W + ny}); } else if(S[nx][ny] == '@' && cost[nx * W + ny] > c + T[i] + P){ cost[nx * W + ny] = c + T[i] + P; q.push({cost[nx * W + ny], nx * W + ny}); } } } } if(cost[xt * W + yt] <= K) cout << "Yes" << endl; else cout << "No" << endl; }