백준 13141 Ignition

백준 13141 ←클릭

변수 설정

dist: 플로이드 와샬 알고리즘을 수행한 결과값 저장 배열
lines: 간선의 정보 저장
INFO: 간선의 정보를 저장하기 위한 구조체, S(시작점), E(끝점), L(길이)로 구성
max_len: 특정 노드에서 시작한 경우 해당 그래프를 모두 지우기 위해 걸리는 시간

아이디어

• 플로이드 와샬을 사용하여 노드 사이의 거리를 모두 구한다.
  
  
• 특정 간선이 없어질 때까지 걸리는 시간은 $\frac{(한쪽 노드까지의 거리) + (다른쪽 노드까지의 거리) + (간선의 길이)}{2}$
  
  
• 가장 노드를 시작점으로 설정하여 brute force방식으로 가장 작은 시간 탐색

시간 복잡도

플로이드 와샬을 적용하는 데에 $O(N^3)$, brute force를 적용하는데 $O(MN)$으로 시간 복잡도는 $O(N^3)$이다.

증명

• a, b, c는 플로이드 와샬을 통해 구해진 최단 거리이다. (고로 b <= a + c)
  
  
• c 간선이 없어지려면 S에서 시작한 불이 near노드에 먼저 도착을 하고, far을 경유해서 오는 불과 중간에서 만난다. (고로 b <= a + c 이기 때문에 far에 도착하기 전에 c가 다 타지는 않는다.)
  
  
• 불은 두갈래 길로 움직이고 총 이동 거리는 a+ b + c이기 때문에 $\frac{a+b+c}{2}$의 시간이 지나면 c가 모두 탄다.

코드

github

#define _CRT_SECURE_NO_WARNINGS
#define INF 987654321
#define ll long long
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool print = false;
int N, M;
int dist[201][201];
struct INFO {
	int S, E, L;
};
vector<INFO> lines(20000);

int main() {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int start, end, length;
		cin >> start >> end >> length;
		lines[i].S = start;
		lines[i].E = end;
		lines[i].L = length;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) dist[i][j] = 0;
			else dist[i][j] = INF; //간선이 없는 경우
		}
	}
	for (int i = 0; i < M; i++) {
		dist[lines[i].S][lines[i].E] = min(dist[lines[i].S][lines[i].E], lines[i].L);
		dist[lines[i].E][lines[i].S] = min(dist[lines[i].S][lines[i].E], lines[i].L);
	}

	for (int m = 1; m <= N; m++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				dist[s][e] = min(dist[s][e], dist[s][m] + dist[m][e]); //floyd warshall
			}
		}
	}

	ll ans = INF;
	for (int s = 1; s <= N; s++) {
		ll max_len = 0;
		if (print) cout << "starting point: " << s << endl;
		for (int i = 0; i < M; i++) {
			int one = lines[i].S;
			int two = lines[i].E;
			ll len = (dist[s][one] + dist[s][two] + lines[i].L);
			max_len = max(max_len, len);
			if (print) printf("one: %d, two: %d, len: %2f, max_len: %2f\n", one, two, len, max_len);
		}
		if (print) cout << s << " 에서 시작하는 최대 시간: " << max_len << endl;
		ans = min(ans, max_len);
		if (print) cout << "현재ans: " << ans << endl;
	}
	cout << fixed;
	cout.precision(1);
	cout << ans / 2 << "." << (ans%2) * 5;
	return 0;
}