結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー hogeover30
提出日時 2015-04-14 02:36:56
言語 C++11（廃止可能性あり）
(gcc 15.2.0 + boost 1.89.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,245 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 871 ms
コンパイル使用メモリ 61,020 KB
最終ジャッジ日時 2024-11-14 19:01:38
合計ジャッジ時間 1,528 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘int dijkstra(int, int)’:
main.cpp:19:9: error: ‘tie’ was not declared in this scope
   19 |         tie(cost, p)=q.top(); q.pop();
      |         ^~~
main.cpp:4:1: note: ‘std::tie’ is defined in header ‘<tuple>’; did you forget to ‘#include <tuple>’?
    3 | #include <queue>
  +++ |+#include <tuple>
    4 |

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
const int inf=10000000;
int L[210][210];
int dr[]={-1, 0, 1, 0}, dc[]={0, -1, 0, 1};
int n, v, ox, oy;

int dijkstra(int s, int t)
{
    priority_queue<pair<int, int>> q;
    vector<int> d(n*n, inf);
    d[s]=L[s/n][s%n];
    q.emplace(0, s);
    while (q.size()) {
        int cost, p;
        tie(cost, p)=q.top(); q.pop();
        cost=-cost;
        int r=p/n, c=p%n;
        if (cost>d[p]) continue;
        for(int i=0;i<4;++i) {
            int nr=r+dr[i], nc=c+dc[i];
            if (nr<0 or nr>=n or nc<0 or nc>=n) continue;
            int np=nr*n+nc;
            if (d[np]>cost+L[nr][nc]) {
                d[np]=cost+L[nr][nc];
                q.emplace(-d[np], np);
            }
        }
    }
    return d[t];
}


int main()
{
    while (cin>>n>>v>>ox>>oy) {
        for(int i=0;i<n;++i) for(int j=0;j<n;++j) cin>>L[i][j];
        if (dijkstra(0, n*n-1)<v)
            cout<<"YES";
        else if (ox and oy) {
            --ox, --oy;
            int x=dijkstra(0, oy*n+ox);
            int y=dijkstra(oy*n+ox, n*n-1);
            cout<<(v>x and (v-x)*2>y ? "YES" : "NO");
        }
        else
            cout<<"NO";
        cout<<endl;
    }
}
0