[Python] 백준 13141 - Ignition

 

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

풀이

불을 N번 정점에서 붙인다고 하자.

불길이 어떤 정점에 도달하는 시간은 최단거리 알고리즘을 이용하면 구할 수 있다.

A, B를 잇는 길이 L인 간선이 다 타는데 걸리는 시간은 (dist[N][A] + dist[N][B] + L)/2 이다.

N과 M이 충분히 작으므로 플로이드-워셜 알고리즘과 브루트포스 알고리즘을 이용하면 답을 구할 수 있다.

시간복잡도는 O(N^3 + MN)이다.

 

import sys
input = sys.stdin.readline
INF = 9_999_999
N, M = map(int, input().split())

dist = [[INF]*(N+1) for _ in range(N+1)]
lines = []

for i in range(M):
    S, E, L = map(int, input().split())
    lines.append((S, E, L))
    dist[S][E] = dist[E][S] = min(L, dist[S][E])

for i in range(1, N+1):
    dist[i][i] = 0

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


ans = [0]*(N+1)
for start in range(1, N+1):
    for S, E, L in lines:
        ans[start] = max(ans[start], (dist[start][S] + dist[start][E] + L)/2)

print(min(ans[1:]))