結果
問題 | No.20 砂漠のオアシス |
ユーザー | peroon |
提出日時 | 2019-05-13 21:58:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 5,000 ms |
コード長 | 4,579 bytes |
コンパイル時間 | 1,744 ms |
コンパイル使用メモリ | 188,512 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-07-08 08:21:56 |
合計ジャッジ時間 | 2,585 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }#define FOR(i,a,b) for(ll i=(a);i<(b);++i)#define ALL(v) (v).begin(), (v).end()#define p(s) cout<<(s)<<endl#define p2(s, t) cout << (s) << " " << (t) << endl#define br() p("")#define pn(s) cout << (#s) << " " << (s) << endl#define p_yes() p("YES")#define p_no() p("NO")const ll mod = 1e9 + 7;const ll inf = 1e18;template < typename T >void vprint(T &V){for(auto v : V){cout << v << " ";}cout << endl;}struct Edge{ll to;ll cost;Edge(ll to, ll cost): to(to), cost(cost) {}Edge(){to = 0;cost = 0;}};struct Node{ll distance;ll index;Node(ll d, ll i){distance = d;index = i;}Node(){}bool operator<(const Node &another) const{return distance < another.distance;}bool operator>(const Node &another) const{return distance > another.distance;}};struct Dijkstra{vector<ll> d;vector<vector<Edge> > graph;vector<bool> done;// ノード数を入れるvoid initialize(ll size){d.resize(size);done.resize(size);graph.resize(size);reset();}void reset(){ll N = graph.size();FOR(i, 0, N){d[i] = inf;done[i] = false;}}ll distance(int i){if(d.size()<=i) return -1;return d[i];}void print_graph(){FOR(i, 0, graph.size()){cout << i << " -> ";for(auto edge : graph[i]){cout << edge.to << " ";}cout << endl;}p("distance");FOR(i, 0, graph.size()){ll d = distance(i);cout << i << " " << d << endl;}}void register_edge(ll a, ll b, ll cost){auto edge = Edge(b, cost);graph[a].push_back(edge);}void calc_shortest_path(ll from=0){priority_queue<Node, vector<Node>, greater<Node> > que;auto node = Node();// 始点node.index = from;node.distance = 0;que.push(node);while(!que.empty()){// 1番distanceが小さいノードNode n = que.top();que.pop();if(done[n.index]){continue;}done[n.index] = true;d[n.index] = n.distance;auto edge_list = graph[n.index];for(auto edge : edge_list){// 短くなるノードがあればif(!done[edge.to] && n.distance + edge.cost < d[edge.to]){ll shorter_distance = n.distance + edge.cost;que.push(Node(shorter_distance, edge.to));}}}}};int main(){cin.tie(0);ios::sync_with_stdio(false);// inputll N, V, Ox, Oy;cin >> N >> V >> Ox >> Oy;Ox--;Oy--;vector<vector<ll> > A(N);FOR(i, 0, N){FOR(j, 0, N){ll L;cin >> L;A[i].push_back(L);}}auto dij = Dijkstra();dij.initialize(N*N);// よこFOR(y, 0, N){FOR(x, 0, N-1){ll cost0 = A[y][x];ll cost1 = A[y][x+1];ll index = N*y + x;dij.register_edge(index, index+1, cost1);dij.register_edge(index+1, index, cost0);}}// たてFOR(x, 0, N){FOR(y, 0, N-1){ll cost0 = A[y][x];ll cost1 = A[y+1][x];ll index = N*y + x;dij.register_edge(index, index+N, cost1);dij.register_edge(index+N, index, cost0);}}dij.calc_shortest_path();ll d = dij.distance(N*N-1);ll rest_HP = V - d;if(rest_HP>0){p_yes();return 0;}// 直行できなかった場合は以下// オアシスがないif(Ox==-1 && Oy==-1){p_no();return 0;}d = dij.distance(N*Oy + Ox);rest_HP = V - d;if(rest_HP<=0){p_no();return 0;}rest_HP *= 2;// オアシスdij.reset();dij.calc_shortest_path(N*Oy + Ox);d = dij.distance(N*N-1);if(rest_HP-d>0){p_yes();}else{p_no();}return 0;}