結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー hogeover30
提出日時 2015-02-24 21:57:30
言語 C++11
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,167 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 339 ms
コンパイル使用メモリ 74,608 KB
最終ジャッジ日時 2026-05-10 04:11:02
合計ジャッジ時間 931 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:24:13: error: 'tie' was not declared in this scope
   24 |             tie(d, r, c)=q.top(); q.pop();
      |             ^~~
main.cpp:4:1: note: 'std::tie' is defined in header '<tuple>'; this is probably fixable by adding '#include <tuple>'
    3 | #include <queue>
  +++ |+#include <tuple>
    4 | 
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/vector:68,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/queue:69,
                 from main.cpp:3:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >]':
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_vector.h:561:7:   required from 'std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue() [with _Seq = std::vector<std::tuple<int, int, int>, std::allocator<std::tuple<int, int, int> > >; _Requires = void; _Tp = std::tuple<int, int, int>; _Sequence = std::vector<std::tuple<int, int, int>, std::allocator<std::tuple<int, int, int> > >; _Compare = std::less<std::tuple<int, int, int> >]'
  561 |       vector() = default;
      |       ^~~~~~
main.cpp:20:46:   required from here
   20 |         priority_queue<tuple<int, int, int>> q;
      |                                              ^
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_vector.h:376:49: error: invalid use of incomplete type 'class std::tuple<int, int, int>'
  376 |                       _M_impl._M_end_of_storage - _M_impl._M_start);
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_algobase.h:64,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/string:53,

ソースコード

diff #
raw source code 

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

using namespace std;
const int inf=100000;
int cost[210][210], a[210][210];
int dr[]={-1, 0, 1, 0}, dc[]={0, -1, 0, 1};

int main()
{
    int n, v, ox, oy;
    while (cin>>n>>v>>ox>>oy) {
        ox--, oy--;
        for(int i=0;i<n;++i) for(int j=0;j<n;++j) {
            cin>>a[i][j];
            cost[i][j]=100000;
        }
        cost[0][0]=a[0][0];
        priority_queue<tuple<int, int, int>> q;
        q.emplace(-cost[0][0], 0, 0);
        while (q.size()) {
            int d, r, c;
            tie(d, r, c)=q.top(); q.pop();
            d=-d;
            if (d>cost[r][c]) 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;
                if (cost[nr][nc]>d+a[nr][nc]) {
                    cost[nr][nc]=d+a[nr][nc];
                    q.emplace(-d-a[nr][nc], nr, nc);
                }
            }
        }
        if (cost[n-1][n-1]<v or (ox>=0 and ox>=0 and 2*(v-cost[oy][ox])>cost[n-1][n-1]-cost[oy][ox]))
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}
0