BOJ13141 Ignition

 

 

BOJ13141 Ignition

 

그래프가 주어지고, vertex 중 한 개에 불을 질렀을 때 그래프가 모두 타는 최소 시간을 출력

불은 1초에 1만큼 태울 수 있고 어디에 불을 붙여도 그래프가 반드시 전체 다 탈 수 있는 경우만 주어지며

시점과 종점이 같은 edge도 주어지고, 같은 시점과 같은 종점 사이 여러 개의 edge가 존재할 수 있다.

 

 

두 가지가 필요하다.

1. 한 vertex에 불이 도달할 수 있는 최소 시간

2. 두 vertex 간 edge가 모두 타는 시간

 

1의 경우

같은 vertex라도 불을 어디에 붙이느냐에 따라 값이 다르다.

결국엔 all vertex → all vertex의 최단거리를 구해야 하므로 floyd-warshall로 구한다.

 

2의 경우

두 vertex 간 가장 긴 edge만을 고려하면 된다. 가장 긴 edge가 탈 동안 짧은 것들은 다 탈 것이기 때문

edge가 다 타는 데에 걸리는 시간은 아래를 참고하자.

vertex i, j 사이 가장 긴 edge의 길이가 10,

i에는 2초부터, j에는 4초부터 불이 붙기 시작한다고 하자.

j에 불이 붙기까지, i부터 edge를 2만큼 태울 수 있다.

4초부터는 edge가 양방향에서 타기 때문에 이후 4초 안에 edge가 탄다.

식으로 나타내면 아래와 같다.

$4+\frac{1}{2}\left ( 10-\left ( 4-2 \right ) \right )=\frac{1}{2}\left ( 10+4+2\right )$

 

N이 작기 때문에 모든 vertex에 대해서 위를 조사하면 된다.

 

 

 

코드

 

e[N][N] e[i][j] i에서 j까지 path중 mincost, 즉 i에 불을 붙였을 때 j에 불이 붙는 시간

E[N][N] E[i][j] i와 j사이 edge 중 가장 긴 edge 길이

 

사실 처음에 큐를 이용해서 풀었는데 굳이 필요없다는 걸 깨달아서 for문으로 바꿨다. 메모리도 메모리인데 시간이 세 배 정도 차이 났다..

line45: 진작 2로 안 나눴기 때문에 출력할 때 나눠준다.

#include <cstdio>
#include <algorithm>
using namespace std;

int e[201][201], E[201][201];
int main() {
	int N, M, a, b, c;

	// Get Input
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) e[i][j] = 987654321;
		e[i][i] = 0;
	}
	while (M--) {
		scanf("%d%d%d", &a, &b, &c);
		e[a][b] = e[b][a] = min(e[a][b], c);
		E[a][b] = E[b][a] = max(E[a][b], c);
	}

	// Floyd-Warshall
	for (int k = 1; k <= N; ++k) {
		for (int i = 1; i <= N; ++i) {
			for (int j = 1; j <= N; ++j)
				e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
		}
	}

	// Find Answer
	int ANS = 987654321, TMP;
	for (int n = 1; n <= N; ++n) {
		// Find max dist when we burn "n"
		// time of burning E[i][j] = A + (E[i][j]-(A-B))/2 = (A+B+E[i][j])/2
		// where A=max(e[n][i],e[n][j]), B=min(e[n][i],e[n][j])
		TMP = 0;
		for (int i = 1; i <= N; ++i) {
			int eni = e[n][i];
			for (int j = i; j <= N; ++j) {
				if (!E[i][j]) continue;
				TMP = max(TMP, eni + e[n][j] + E[i][j]);
			}
		}
		ANS = min(ANS, TMP);
	}
	printf("%.1f", (double)ANS / 2.0);

	return 0;
}

 

 

사실은 이런 노가다를 통해서야 확신할 수 있었다.. 아래 테케 답은 7.0