結果

問題 No.971 いたずらっ子
ユーザー kya_skikya_ski
提出日時 2020-01-18 13:13:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,709 ms / 2,000 ms
コード長 1,570 bytes
コンパイル時間 2,066 ms
コンパイル使用メモリ 178,816 KB
実行使用メモリ 323,456 KB
最終ジャッジ日時 2024-04-25 02:08:23
合計ジャッジ時間 16,597 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,695 ms
323,356 KB
testcase_01 AC 1,662 ms
323,456 KB
testcase_02 AC 1,238 ms
241,344 KB
testcase_03 AC 1,709 ms
323,376 KB
testcase_04 AC 1,475 ms
304,544 KB
testcase_05 AC 1,588 ms
323,360 KB
testcase_06 AC 1,185 ms
248,576 KB
testcase_07 AC 11 ms
6,016 KB
testcase_08 AC 371 ms
87,228 KB
testcase_09 AC 354 ms
83,212 KB
testcase_10 AC 8 ms
5,888 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int dh[2] = {0, 1}, dw[2] = {1, 0};
template <typename T> vector<T> dijkstra(const vector<vector<pair<int, T>>> &G, int s){
    using P = pair<T, int>;
    const T inf = numeric_limits<T>::max();
    vector<T> ret(G.size(), inf); ret[s] = 0;
    priority_queue<P, vector<P>, greater<P>> que;
    que.emplace(ret[s], s);
    while (!que.empty()) {
        T dist; int node;
        tie(dist, node) = que.top(); que.pop();
        if (ret[node] < dist) continue;
        for (auto &e : G[node]) {
            int next_node; T next_dist;
            tie(next_node, next_dist) = e;
            if (ret[next_node] > ret[node] + next_dist) {
                ret[next_node] = ret[node] + next_dist;
                que.emplace(ret[next_node], next_node);
            }
        }
    }
    return ret;
}

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; i++) cin >> S[i];
    
    auto idx = [&](int h, int w) { return h*W+w; };
    vector<vector<pair<int, long long>>> G(H*W);
    for (int h = 0; h < H; h++) for (int w = 0; w < W; w++) {
        int from = idx(h, w);
        for (int i = 0; i < 2; i++) {
            int nh = h + dh[i], nw = w + dw[i], to = idx(nh, nw);
            if (nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
            if (S[nh][nw] == 'k') G[from].emplace_back(to, nh+nw+1);
            else G[from].emplace_back(to, 1);
        }
    }
    
    vector<long long> dist = dijkstra(G, 0);
    cout << dist[idx(H-1, W-1)] << endl;
    return 0;
}
0