結果
問題 | No.20 砂漠のオアシス |
ユーザー | fine |
提出日時 | 2017-02-28 15:56:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,368 bytes |
コンパイル時間 | 2,118 ms |
コンパイル使用メモリ | 183,004 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-10-13 05:49:57 |
合計ジャッジ時間 | 2,810 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 WA * 1 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct Node {int at;int cost;int prev;Node(int at, int cost, int prev) : at(at), cost(cost), prev(prev) {}bool operator>(const Node &s) const {if (cost != s.cost) return cost > s.cost;if (prev != s.prev) return prev > s.prev; //最短経路を辞書順最小にする(省略可)return at > s.at;}};struct Edge {int to;int cost;Edge(int to, int cost) : to(to), cost(cost) {}};typedef vector<vector<Edge> > AdjList; //隣接リストconst int INF = 1000000000;const int NONE = -1;AdjList graph;//sは始点、mincは最短経路のコスト、Prevは最短経路をたどる際の前の頂点void dijkstra(int s, vector<int> &minc, vector<int> &Prev){priority_queue<Node, vector<Node>, greater<Node> > pq;pq.push(Node(s, 0, NONE));while(!pq.empty()) {Node cur = pq.top();pq.pop();if (minc[cur.at] <= cur.cost) continue;minc[cur.at] = cur.cost;Prev[cur.at] = cur.prev;for(int i = 0; i < (int)graph[cur.at].size(); i++) {Edge e = graph[cur.at][i];if (minc[e.to] > cur.cost + e.cost) {pq.push(Node(e.to, cur.cost + e.cost, cur.at));}}}}const int dh[] = {1, -1, 0, 0};const int dw[] = {0, 0, 1, -1};int main() {cin.tie(0);ios::sync_with_stdio(false);int n, v, ox, oy;cin >> n >> v >> ox >> oy;ox--;oy--;vector< vector<int> > L(n, vector<int>(n));for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> L[i][j];}}graph.resize(n * n);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {for (int k = 0; k < 4; k++) {int h = i + dh[k], w = j + dw[k];if (h < 0 || h >= n || w < 0 || w >= n) continue;graph[i * n + j].emplace_back(h * n + w, L[h][w]);}}}vector<int> minc(n * n, INF), Prev(n * n, NONE);dijkstra(0, minc, Prev);if (minc[n * n - 1] < v) {cout << "YES" << endl;return 0;}if (ox == -1 && oy == -1) {cout << "NO" << endl;return 0;}if (minc[oy * n + ox] >= v) {cout << "NO" << endl;return 0;}v -= minc[oy * n + ox];v *= 2;minc.resize(n * n, INF);Prev.resize(n * n, NONE);dijkstra(oy * n + ox, minc, Prev);cout << (minc[n * n - 1] < v ? "YES" : "NO") << endl;return 0;}