[BOJ/Platinum 5] 백준 13141 Ignition(C++)

문제 링크

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

13141번: Ignition

문제

서훈이는 오늘 있었던 알고리즘 과목 기말고사를 망쳐서 기분이 좋지 않다. 서훈이는 스트레스도 풀 겸 시험 문제로 나온 그래프를 불로 태우려고 한다.

서훈이는 그래프의 정점 (위 그림에서 동그라미로 표시된 곳) 중 한 곳에 불을 붙일 수 있다. 정점에 불이 붙으면 곧바로 노드와 연결된 간선을 따라서 불이 전달된다. 간선 위에서는 불은 1초당 1만큼의 거리를 이동한다. 만약 어떤 간선의 양 끝 정점에 불이 붙은 경우 불은 간선의 중앙까지 태운 후 꺼진다.

서훈이는 그래프를 최대한 빠른 시간 안에 전부 태우고 싶어한다. 서훈이를 도와 어떤 정점에 불을 붙일지 구하는 프로그램을 작성하여라. 단, 위 그림에서 간선끼리 교차하는 것은 무시한다.

입력

첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000)

두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100)

시작점과 끝점이 같은 간선도 있을 수 있으며, 특정 두 정점을 직접 연결하는 간선의 수가 여러 개일 수 있다. 또한, 그래프의 모든 정점들은 간선들을 통해서 연결되어 있다.

출력

주어진 그래프를 모두 태우는 데 걸리는 최소 시간을 출력한다. 답은 소수점 아래 한 자리까지 출력한다. 문제의 특성 상 오차가 생길 일이 없으므로 출력 데이터와 정확히 일치해야 정답으로 처리한다.

예제 입력 1

5 8
1 2 4
1 2 6
1 5 6
2 4 4
4 5 4
3 4 6
3 4 6
3 3 4

예제 출력 1

9.0

예제 입력 2

5 10
1 2 1
2 3 1
3 4 1
4 5 1
1 3 10
2 4 10
3 5 10
1 4 7
2 5 7
1 5 9

예제 출력 2

6.5

알고리즘 분류

• 최단 거리 알고리즘
• 브루트포스 알고리즘

풀이

Vertex 수가 최대 200개이기 때문에 브루트포스을 활용해서 모든 정점에 한 번씩 불을 붙이고 그래프가 전부 타는 시간의 최솟값을 구할 수 있다.

우선 주어진 정보를 활용하여 플로이드-와샬로 각 정점과 정점 간의 최단 거리를 구한다.

그리고 1번 정점부터 N번 정점까지 한 번씩 불을 붙이고, 각 정점이 불에 타는 최소의 시간을 구한다.

그리고 모든 간선이 불에 타는 시간을 구하는데, 조건에 맞춰서 구한다.

우선 간선 하나가 불에 다 타는 시간(A)은 간선의 길이 + 간선과 연결된 두 정점 중 불이 더 빨리 붙는 정점의 불이 붙는 시간이다.

1. 양쪽 정점이 다 불에 타지 않은 경우, 간선에 붙은 불이 꺼지는 시간은 A초만큼이다.

2. 양쪽 정점이 B초에 전부 불에 탄 경우, 간선에 붙은 불이 꺼지는 시간은 B + (A - B) / 2이다.

생각할 때는 몰랐는데 말로 설명하기 되게 어렵다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 201
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	int S, E, L;
};

int N, M;
int Ignited[MAX];
int DP[MAX][MAX];
vector<INFO> Edge;
double answer = INF;

void input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) {
				continue;
			}
			DP[i][j] = INF;
		}
	}
	for (int i = 0; i < M; i++) {
		int S, E, L;
		cin >> S >> E >> L;
		Edge.push_back({ S,E,L });
		DP[S][E] = min(DP[S][E], L);
		DP[E][S] = min(DP[E][S], L);
	}
}

void Settings() {
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (DP[i][j] > DP[i][k] + DP[k][j]) {
					DP[i][j] = DP[i][k] + DP[k][j];
				}
			}
		}
	}
}

void init() {
	for (int i = 1; i <= N; i++) {
		Ignited[i] = 0;
	}
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		init();
		double Tmp = 0;
		for (int j = 1; j <= N; j++) {
			Ignited[j] = DP[i][j];
		}
		for (int j = 0; j < Edge.size(); j++) {
			int S = Edge[j].S;
			int E = Edge[j].E;
			int L = Edge[j].L;
			if ((S != i) && (E != i)) {
				L += min(Ignited[S], Ignited[E]);
			}
			double T1 = max(Ignited[S], Ignited[E]);
			double T2 = (double)(L - T1) / (double)2;
			if (T2 < 0) {
				T2 = 0;
			}
			double T = T1 + T2;
			Tmp = max(Tmp, T);
		}
		answer = min(answer, Tmp);
	}
	cout << fixed;
	cout.precision(1);
	cout << answer << "\n";
}

int main() {
	FASTIO
	input();
	Settings();
	Find_Answer();

	return 0;
}