結果

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

ソースコード

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