Ignition(점화) (BOJ 13141)

문제

문제 설명

• 이 문제는 단순히 모든 정점을 방문하는 것이 아니라 그래프의 모든 간선을 이동해야 하는 경우이다.
• 조심해야 할 부분은 여러 개의 간선이 연결된 정점의 경우에는 간선이 점화되는 시간이 달라질 수도 있다.

문제 해설

문제를 풀 때는 두가지를 고려할 필요가 있음.

• 정점 간의 이동 시간의 최솟값을 구해준다. (플로이드 와샬)
•  모든 정점의 에서 모든 간선으로 이동하는 시간의 최솟값을 구해준다. (브루트 포스)

1. 플로이드 와샬과 같은 경우에는 기본적으로 우리가 아는 알고리즘을 사용하여서 구해주면 된다.
2. 모든 간선을 점화하는데점화하는 데 걸리는 시간과 같은 경우는 한 정점에서 모든 간선을 점화하는 데 걸리는 시간의 최댓값을 구해주고 이러한 최댓값들의 최솟값을 구하면 된다. 하지만 최댓값을 구하는 데에서 문제가 발생하는데, 이러한 부분은 아래와 같이 해결할 수 있다.

(점화를 시작한 정점에서 i정점 까지의 최소 점화 시간  + 점화를 시작한 정점에서 j정점까지의 최소 점화 시간 + i와 j정점 사이에 존재하는 간선의 점화 시간) / 2

 

결론적으로는 처음 정점에서 부터 i번과 j번 사이의 정점을 모두 태워버리는 대 걸리는 시간은 전체시간의 절반이 된다.

최종 코드

#include<iostream>
#include<vector>
#include<iomanip>
using namespace std;
const int inf = 1e9 + 4;
struct P {int a, b, c;};
int n, m;
int d[204][204];
vector<P> v;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	fill(&d[0][0], &d[0][0] + 204 * 204, inf);
	for (int i = 1; i <= n; i++) d[i][i] = 0;
	for (int i = 1,x,y,z; i <= m; i++) {
		cin >> x >> y >> z;
		v.push_back({ x,y,z });
		d[x][y] = min(d[x][y], z);
		d[y][x] = min(d[x][y], z);
	}
	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]);
			}
		}
	}
	int mn = inf;
	for (int i = 1; i <= n; i++) {
		int mx = 0;
		for (auto j : v) {
			mx = max(mx, d[i][j.a] + d[i][j.b] + j.c);
		}
		mn = min(mx, mn);
	}
	cout << fixed << setprecision(1) << float(mn) / 2.0;
}

 

제일 먼저 플로이드 와샬을 사용하여서 정점 간의 최소 거리를 찾아준다.

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]);
			}
		}
	}

 

그런 다음 i (점화 지점) 에서 j.a 정점, j.b정점까지의 시간과 j.c (j.a와 j.b사이 시간)의 합의 최댓값을 구해준다.

mx = max(mx, d[i][j.a] + d[i][j.b] + j.c);

 

이미지 클릭