ABC020 C問題（壁抜け）を解く

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<ll, pair<int, int>> PP;
#define INF (1LL << 60)

int main()
{
	int h, w;
	ll t;
	cin >> h >> w >> t;
	vector<string> s(h);
	for (int i = 0; i < h; ++i) {
		cin >> s[i];
	}

	int si = -1;
	int sj = -1;
	int gi = -1;
	int gj = -1;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			if (s[i][j] == 'S') {
				si = i;
				sj = j;
				s[i][j] = '.';
			} else if (s[i][j] == 'G') {
				gi = i;
				gj = j;
				s[i][j] = '.';
			}
		}
	}

	int di[4] = {1, 0, -1, 0};
	int dj[4] = {0, 1, 0, -1};

	auto is_OK = [&](ll mid) -> bool {
		priority_queue<PP, vector<PP>, greater<PP>> que;
		vector<vector<ll>> dist(h, vector<ll>(w, INF));

		que.push(make_pair(0, make_pair(si, sj)));
		dist[si][sj] = 0;
		while (!que.empty()) {
			auto pp = que.top();
			que.pop();
			int now_i = pp.second.first;
			int now_j = pp.second.second;
			if (dist[now_i][now_j] < pp.first) {
				continue;
			}
			for (int d = 0; d < 4; ++d) {
				int next_i = now_i + di[d];
				int next_j = now_j + dj[d];
				if ((next_i < 0) || (h <= next_i)) {
					continue;
				}
				if ((next_j < 0) || (w <= next_j)) {
					continue;
				}
				ll weight;
				if (s[next_i][next_j] == '#') {
					weight = mid;
				} else {
					weight = 1;
				}
				if (dist[next_i][next_j] > dist[now_i][now_j] + weight) {
					dist[next_i][next_j] = dist[now_i][now_j] + weight;
					que.push(make_pair(dist[next_i][next_j],
									   make_pair(next_i, next_j)));
				}
			}
		}
		return dist[gi][gj] <= t;
	};

	ll ng = 1000000001;
	ll ok = 1;
	while (abs(ok - ng) > 1) {
		ll mid = (ok + ng) / 2;
		if (is_OK(mid)) {
			ok = mid;
		} else {
			ng = mid;
		}
	}

	cout << ok << endl;

	return 0;
}