[백준/13141] Ignition (Python)

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

13141번: Ignition

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:40:28

 

---

 

문제 설명

 

 

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

 

 

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

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

 

 

입력 및 출력

 

입력

 

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

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

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

 

출력

 

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

 

입력 예시

 

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

 

출력 예시

 

9.0

 

 

---

 

풀이

 

우리는 정점과 다른 정점을 잇는 간선 길이를 최솟값과 최댓값을 나누어 저장할 필요가 있다.

 

• 정점 간 최소 방문 거리는 최소 간선을 통해 발생하고
• 우리가 고려해야 할 사항, 즉 두 정점에서 불이 붙어 간선 위에서 두 불이 만날 경우는 최대 간선에서 발생하며, 동시에 최대 간선에서 최대 시간이 나온다.

 

또한, 우리는 각 점에서 불을 붙였을 때 모든 정점에 도달하는 시간이 필요하고, 최대 N = 200임을 알 수 있다. 즉 플로이드-와셜 알고리즘을 통해 모든 정점간의 최소 거리를 구할 수 있겠다.

 

다음은 간선의 중앙에서 타는 경우를 살펴보자. 

 

• 두 정점을 직접적으로 연결하는 경로(최대 간선)가 존재하고
• 시작 정점에서 두 정점까지의 최소 거리차가 최대 간선과 일치하지 않는다면

 

최대 간선의 중앙에서 두 불이 만나게 된다. 이 때 두 정점의 최소 도착 시간을 vi, vj라 두고, 최대 간선 길이를 L이라 두자. 나중에 불이 정점에 도달한 시점(vi)에, 먼저 정점에 도달한 불은 그 차(vi - vj)만큼 최대 간선을 태웠을 것이다. 남은 간선의 길이는 L - (vi - vj) 이므로 그 절반 시간인 (L - vi + vj) / 2 시간 후에 두 불이 한 지점에서 만나게 된다. 정점의 최소 시간, 그리고 간선 중앙에서 타는 경우를 모두 고려했을 때의 최대 시간이 한 정점에서 시작했을 때 모든 그래프를 태우는 시간이다. 모든 정점에 대해서 위를 고려하면 된다.

 

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline
MAX = float('inf')

N, M = map(int, input().split())
min_edge = [[MAX]*(N+1) for _ in range(N+1)]
max_edge = [[0]*(N+1) for _ in range(N+1)]
ans = MAX
for _ in range(M) :
  S, E, L = map(int, input().split())
  min_edge[E][S] = min_edge[S][E] = min(min_edge[S][E], L)
  max_edge[E][S] = max_edge[S][E] = max(max_edge[S][E], L)

for k in range(1, N+1) :
  for i in range(1, N) :
    for j in range(i+1, N+1) :
      if i == k or j == k :
        continue
      if min_edge[i][j] > min_edge[i][k] + min_edge[k][j] :
        min_edge[i][j] = min_edge[j][i] = min_edge[i][k] + min_edge[k][j]

for k in range(1, N+1) :
  min_edge[k][k] = 0
  result = 0.
  for i in range(1, N+1) :
    for j in range(i, N+1) :
      if not max_edge[i][j] :
        continue
      result = max(result, min_edge[k][i], min_edge[k][j])
      if abs(min_edge[k][i] - min_edge[k][j]) != max_edge[i][j] :
        result = max(result, max(min_edge[k][i], min_edge[k][j]) + (max_edge[i][j] - abs(min_edge[k][i] - min_edge[k][j])) / 2)
  ans = min(ans, result)

print('{:.01f}'.format(ans))

 

풀이 완료!