結果

問題 No.971 いたずらっ子
コンテスト
ユーザー kya_ski
提出日時 2020-01-18 13:09:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,419 ms / 2,000 ms
コード長 2,259 bytes
コンパイル時間 2,138 ms
コンパイル使用メモリ 183,240 KB
実行使用メモリ 324,480 KB
最終ジャッジ日時 2024-11-07 11:38:16
合計ジャッジ時間 13,826 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int dh[2] = {0, 1}, dw[2] = {1, 0};
vector<long long> dijkstra(const vector<vector<pair<int, long long>>> &G, int s){
    struct RadixHeap {
        using P = pair<long long, int>;
        int bsr(long long x){ return (x == 0) ? -1 : 63-__builtin_clz(x); }
        vector<P> v[65];
        long long last, sz;
        RadixHeap() : last(0), sz(0) { }
        bool empty () { return (sz == 0); }
        void push(long long x, int u) { sz++; v[bsr(x^last)+1].emplace_back(x, u); }
        P pop () {
            if (!v[0].size()) {
                int i = 1;
                while (!v[i].size()) { i++; }
                last = min_element(v[i].begin(), v[i].end())->first;
                for (auto x : v[i]) { v[bsr(x.first^last)+1].emplace_back(x); }
                v[i].clear();
            }
            P res = v[0].back(); sz--; v[0].pop_back(); return res;
        }
    };
    const long long inf = INT64_MAX;
    vector<long long> ret(G.size(), inf); ret[s] = 0;
    RadixHeap rh; rh.push(ret[s], s);
    while (!rh.empty()) {
        long long dist; int node;
        tie(dist, node) = rh.pop();
        if (ret[node] < dist) continue;
        for (auto &e : G[node]) {
            int next_node; long long next_dist;
            tie(next_node, next_dist) = e;
            if (ret[next_node] > ret[node] + next_dist){
                ret[next_node] = ret[node] + next_dist;
                rh.push(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