(백준) 13141번 - Ignition

문제

https://www.acmicpc.net/problem/13141

풀이

특정 간선이 다 타기까지 걸리는 시간

시작점을 $S$, 간선을 $(u, v)$, 간선의 길이를 $L$라고 할 때, 해당 간선이 타는 시간은 $\frac{dist[S][u] + dist[S][v] + L}{2}$이다.

편의상 $dist[S][u] \le dist[S][v]$라고 가정한다. 즉, 불은 정점 $v$보다 $u$에 먼저 도달한다고 하자. $t=dist[S][u]$일 때, 불은 정점 $u$에 도착하며, 간선을 태우기 시작한다. 이후 $t=dist[S][v]$가 되면 정점 $v$에도 불이 도착하며, 반대쪽에서 간선을 태우기 시작한다. 이 시점에서 그동안 탄 간선의 길이는 $dist[S][v] - dist[S][u]$이며, 남은 간선의 길이는 $L-(dist[S][v]-dist[S][u])$이다. 이후 간선은 양뱡향에서 타들어간다. 즉, 타는 속도가 2배가 된다.

남은 간선의 길이를 속도 2로 태우는 시간은 $\frac{L-dist[S][v]+dist[S][u]}{2}$이다. 따라서 간선이 완전히 타버리는 시간은 $dist[S][v]+\frac{L-dist[S][v]+dist[S][u]}{2}$이며, 통분하면 $\frac{dist[S][u] + dist[S][v] + L}{2}$이다.

불이 정점 $u$에 도달하고 $v$에 불이 도달하기 전 간선이 다 타버리는 상황은 최단 경로 특성 상 발생할 수 없다.

$dist[S][v]$는 $S$에서 $v$까지 가는 최단 시간인데, 불이 $u$를 거쳐 간선 $(u, v)$를 타고 $v$에 도달한다면 그 시간은 $dist[S][v]+L$이 된다. 이것이 최단 경로라면 $dist[S][v]=dist[S][u]+L$이 되며, 이보다 더 빠른 경로가 있다면 $dist[S][v] < dist[S][u]+L$이다. 즉, 어떤 상황에서도 $dist[S][v] > dist[S][u]+L$가 될 수 없다($v$에 불이 도착했을 때 남은 간선의 길이가 음수일 수 없다).

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define INF 1e9

using namespace std;

vector<int> graph[201][201]; // graph[i][j] = {l1, l2, ...} : (i, j) 간선의 길이는 l1, l2, ...
int dist[201][201];

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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a][b].push_back(c);
		graph[b][a].push_back(c);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) {
				dist[i][j] = 0;
			}
			else if (graph[i][j].size() != 0) {
				int minLength = *min_element(graph[i][j].begin(), graph[i][j].end());
				dist[i][j] = minLength;
			}
			else {
				dist[i][j] = INF;
			}
		}
	}

	// 각 노드 간 최단 거리를 구한다.
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	// 모든 간선에 대해 다 타기까지의 시간을 구한다.
	// 시작점을 S라고 할 때, 길이 L의 간선 (i, j)가 다 타는 시간은 (dist[S][i] + dist[S][j] + L) / 2
	double ans = 2e9;
	for (int start = 1; start <= n; start++) {
		double tmp = 0.0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (int idx = 0; idx < graph[i][j].size(); idx++) {
					int L = graph[i][j][idx];
					tmp = max(tmp, (double)(dist[start][i] + dist[start][j] + L) / 2.0);
				}
			}
		}

		ans = min(ans, tmp);
	}

	cout << fixed;
	cout << setprecision(1);
	cout << ans;
}

시간복잡도

초기화 과정에서 $M$개의 간선 정보를 저장하는데 $O(M)$, dist 배열을 초기화하는데 $O(N^2)$이다. 총 $O(N^2+M)$이다.

플로이드 - 워셜 알고리즘에서 모든 노드 간 최단 거리를 구하는데 $O(N^3)$이다.

각 출발점으로부터 모든 간선을 순회하며 다 타기까지 걸리는 시간을 구하는데 $O(NM)$이다. 4중 for문이지만 루프 변수가 i, j, idx 인 반복문은 총 연산 횟수가 간선 길이인 $M$에 비례하기 때문이다.

따라서 전체 시간복잡도는 $O(N^3+NM)$이다.

공간복잡도

dist 배열에서 $O(N^2)$, 간선을 저장하는 graph 배열에서 $O(M)$이므로, 총 $O(N^2+M)$이다.