結果

問題 No.20 砂漠のオアシス
ユーザー finefine
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
//smincPrev
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0