백준 9502 Bones’s Battery

https://boj.ma/9502/t

9502번: Bones’s Battery

 

모든 학교 간 이동을 가능하게 하는 최소 배터리 용량을 찾고싶은 문제입니다.

충전은 최대 K번 할 수 있고 시작시 용량이 0이기 때문에 시작할때 반드시 한 번 충전을 해야합니다.

 

용량을 최소한으로 소모하여 이동하는게 이득이기 때문에 어떤 두 정점간 최단경로로 이동하는것이 최적입니다.

 

문제에서 원하는 값은 "최대 K번 충전하여 모든 학교간 이동을 가능하게 하는 충전량의 최소값" 입니다.

완탐을 떠올려 보면

1회 충전 시 충전량이 1일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?

1회 충전 시 충전량이 2일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?

1회 충전 시 충전량이 3일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?

1회 충전 시 충전량이 4일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?

...

1회 충전 시 충전량이 X일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?

처럼 결정 문제로 바꿀 수 있고, 위 결정문제에 대한 정답은 단조성을 보이기 때문에 즉, 특정 용량 이후로는 항상 가능하다는 대답이 나오기 때문에 이분탐색으로 최적화가 가능합니다.

 

모든 정점쌍 간 최단경로를 구해야하고, N이 작기 때문에 플로이드 워셜로 최단경로를 구할 수 있습니다.

 

시간복잡도는 이분탐색으로 가능한 구간에 매 탐색마다 플로이드를 돌리기 때문에

$O(N^3 log_210^{11})$ 이 됩니다.

 

코드 (C++)

#include <bits/stdc++.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define endl "\n"
#define NM 15*15+10
#define MAX 150010
#define BIAS 1048576
#define X first
#define Y second
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
using ll = long long;
using ull = unsigned long long;

int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int dy[8] = { 0, 1, 0, -1, 1, -1, 1, -1 };


int main() {
	fastio;

	int t;
	cin >> t;
	while (t--) {
		int n, K, m;
		cin >> n >> K >> m;
		vector<vector<ll>> dist(n, vector<ll>(n, LINF));

		for (int i = 0; i < n; i++) dist[i][i] = 0;

		for (int i = 0; i < m; i++) {
			ll a, b, c;
			cin >> a >> b >> c;
			dist[a][b] = min(dist[a][b], c);
			dist[b][a] = min(dist[b][a], c);
		}

		for (int k = 0; k < n;k++) {
			for (int i = 0; i < n; i++){
				for (int j = 0; j < n; j++) {
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}

		auto ok = [&](ll x)->bool {
			vector<vector<ll>> tmp(n, vector<ll>(n, INF));
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n;j++) {
					if (i == j) tmp[i][j] = 0;
					else if (dist[i][j] <= x) tmp[i][j] = 1;
				}
			}
			for (int k = 0; k < n;k++) {
				for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						tmp[i][j] = min(tmp[i][j], tmp[i][k] + tmp[k][j]);
					}
				}
			}

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (tmp[i][j] > K)  return false;
				}
			}

			return true;
		};

		ll l = 0, r = LINF;
		ll ans = r;

		while (l <= r) {
			ll mid = l + r >> 1;
			if (ok(mid)) {
				ans = mid;
				r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
		cout << ans << endl;

	}
	

	return 0;
}