Submission #8960674

---

Source Code Expand

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using edge = pair<int, long long>;
using Graph = vector<vector<edge>>;
//#define int long long
int H, W, s, g;
long long T;
int idx (int h, int w) { return h * W + w; }
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

Graph make_graph(const vector<string> &S, long long cost) {
    Graph 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 < 4; i++) {
            int dh = h + dy[i], dw = w + dx[i];
            int to = idx(dh, dw);
            if (dh<0 || H<=dh || dw<0 || W<=dw) continue;
            if (S[dh][dw] == '#') G[from].emplace_back(to, cost);
            else G[from].emplace_back(to, 1LL);
        }
    }
    return G;
}

long long dijkstra(const vector<string> &S, long long cost){
    using Pi = pair<long long, int>;
    const long long INF = 1e18;
    Graph G = make_graph(S, cost);
    vector<long long> ret(G.size(), INF);
    priority_queue<Pi, vector<Pi>, greater<Pi>> que;
    ret[s] = 0;
    que.emplace(ret[s], s);
    while (!que.empty()) {
        long long dist;
        int node;
        tie(dist, node) = que.top();
        que.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;
                que.emplace(ret[next_node], next_node);
            }
        }
    }
    return ret[g];
}

signed main() {
    cin >> H >> W >> T;
    vector<string> S(H);
    for (int i = 0; i < H; i++) {
        cin >> S[i];
        for (int j = 0; j < W; j++) {
            if (S[i][j] == 'S') s = idx(i, j);
            if (S[i][j] == 'G') g = idx(i, j);
        }
    }
    
    long long ok = 0, ng = 1e18;
    while (abs(ok-ng) > 1) {
        long long mid = (ok+ng)/2;
        long long f = dijkstra(S, mid);
        if (f > T) ng = mid;
        else ok = mid;
        //cout << f << endl;
    }
    cout << ok << endl;
    return 0;
}

Submission Info

Judge Result