[백준] 13141 - Iginition (Python)

불이 전파되는 방식을 어떻게 구현해야 할까?
불의 속도는 1이므로 불이 다른 정점으로 전파되는 시간은 정점 사이의 최단거리와 같다.

모든 발화점을 비교해서 그래프가 전부 타는 최소시간을 구해야 하므로 플로이드 워셜 알고리즘을 사용해 모든 정점 사이에서 불이 전파되는 속도를 구해놔야 한다.

간선이 타는 시간을 구현하는 것이 핵심이다. 간선의 길이를 L, 두 정점에 불이 전파되는 시간을 A, B라 하자. A < B를 만족한다면 A일 때 한쪽이 타기 시작하고 B가 될 때 양쪽에 불이 붙는다. 이 시점에 남아있는 길이는 L - (B-A) 가 된다.
이때부터는 2배 빠르게 타오르므로 간선이 모두 타는 시간은 B + (L - (B-A)) / 2 가 될 것이다.

두 정점 사이의 모든 간선이 타는 시간은 가장 긴 간선이 타는 시간과 같으므로 가장 긴 간선만을 태우면 충분하다. 시작점과 끝점이 같은 간선이 존재함을 잊지 말자.

import sys, math
input = sys.stdin.readline

# 플로이드 워셜
def find_dist():
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if i == j:
                    continue 
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

# s는 발화점(시작점)
def ignite(s):
    result = 0
    for i in range(1, n+1):
        for j in range(i, n+1):
        	# 두 정점 사이에 간선이 없는 경우
            if not max_graph[i][j]:
                continue
            # 불이 i와 j에 전파되는 시간, a < b로 정렬
            a, b = sorted([dist[s][i], dist[s][j]])
            # b인 시점에 남아있는 간선의 길이
            remain = max_graph[i][j]-(b-a)
            result = max(result, b + remain/2)
    return result
                
n, m = map(int, input().rstrip().split())
dist = [[0 if i == j else math.inf for j in range(n+1)] for i in range(n+1)]
# 태울 간선이 저장되어 있다.
max_graph = [[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    s, e, l = map(int, input().rstrip().split())
    # dist에는 가장 짧은 간선을 저장한다.
    dist[s][e] = min(dist[s][e], l)
    dist[e][s] = min(dist[e][s], l)
    # max_graph에는 가장 긴 간선을 저장한다.
    max_graph[s][e] = max(max_graph[s][e], l)
    max_graph[e][s] = max(max_graph[e][s], l)
    
find_dist()
min_result = math.inf
for i in range(1, n+1):
    min_result = min(min_result, ignite(i))
print(min_result)