백준 - Ignition (13141)

1. 문제 링크

Ignition

2. 풀이

1 ~ n 번 정점까지 순서대로 다 점화해보면서,
그 중에 모든 그래프가 다 재가 되는 최소 시간을 구하면 됩니다.
최소 시간이려면 당연히 최단 거리 루트를 타는 게 좋으니까
플로이드 와샬도 사용합니다.

재가 되는 시간 구하는 법

초기 상태가 이와 같고, S정점에 점화한 상황을 가정합시다.

3초 후 상황의 그림입니다.
S -> M보다 S -> A -> M 경로가 더 짧기 때문에 이런 그림이 그려집니다.
그렇다면 남은 녹색선인 2는 d[s][e] - d[s][m]으로 구할 수 있습니다. (d는 플로이드 와샬 배열)

이전 상황으로부터 2초 후 상황의 그림입니다.
여기서 우리는 최장선인 5만 주목하면 된다는 사실을 알 수 있습니다!
M -> E로 가는 경로가 수백억개 있다고 해도,
그 중 제일 긴 경로만 우리의 관심 대상이 됩니다.

남은 최장선은 M -> E를 잇는 가장 긴 선의 길이를 a[m][e]라고 할 때,
a[m][e] - (d[s][e] - d[s][m])로 구할 수 있습니다.
이를 remainLen이라 칭할 때, 양 끝에서 타니까 타는 속도는 2배가 됩니다.

전체 코드

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
int n, m;
int d[201][201], a[201][201];

// 플로이드 와샬로 모든 경로 최단 거리로 초기화
void init() {
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

double solve() {
	double ret = INF;

	// 1 ~ n까지 다 점화해본다.
	for (int s = 1; s <= n; s++) {
		double cand = 0;

		for (int m = 1; m <= n; m++) {
			for (int e = 1; e <= n; e++) {
				if (d[m][e] == INF) continue;

				double remainLen = a[m][e] - (d[s][e] - d[s][m]);

				if (remainLen) {
					cand = max(cand, remainLen / 2 + d[s][e]);
				}
			}
		}

		ret = min(ret, cand);
	}

	return ret;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		fill(d[i] + 1, d[i] + 1 + n, INF);
		d[i][i] = 0;
	}

	while (m--) {
		int s, e, l;
		cin >> s >> e >> l;
		d[s][e] = min(d[s][e], l);
		d[e][s] = d[s][e];

		a[s][e] = max(a[s][e], l);
		a[e][s] = a[s][e];
	}

	init();
	cout << fixed;
	cout.precision(1);
	cout << solve();

	return 0;
}