import sys
input = sys.stdin.readline
N,M = map(int,input().split())
DP = [[1e9]*N for i in range(N)]
graph = []
for _ in range(M):
a,b,c = map(int,input().split())
DP[a-1][b-1] = DP[b-1][a-1] = min(DP[a-1][b-1],c)
graph.append((a-1,b-1,c))
for k in range(N):
for i in range(N):
for j in range(N):
DP[i][j] = min(DP[i][j],DP[i][k]+DP[k][j])
for i in range(N):
DP[i][i] = 0
result = 1e9
for i in range(N):
MAX = 0
for a,b,c in graph:
MAX = max(MAX,(DP[i][a]+c+DP[b][i])/2)
result = min(result,MAX)
print(result)
플로이드 워셜로 해결하였다.
기본적인 풀이를 설명하면,
1. 플로이드 워셜 알고리즘으로 각 노드간 최소거리를 측정
2. 모든 노드마다 모든 간선에 대해서 간선을 지우는데 걸리는 시간을 측정하고 ((플로이드 워셜로 측정한 노드간 길이 + 간선의 길이)/2) 각 노드의 간선을 지우는데 걸리는 시간의 최댓값의 최솟값이 곧 결과이다.
실수할 여지가 좀 있는 문제였는데, 일단 자기자신으로 가는 거리를 0으로 초기화시켜주어야 한다. 왜냐하면 자기자신을 지나는 간선을 태우는데 걸리는 시간이 잘못 측정될 수 있기 때문이다. 또, 인접행렬을 만들 때, 같은 노드간에 여러개의 간선이 입력될 수 있기 때문이다.
예제에 위의 예시에 해당하는 경우가 있어서 한결 편하게 풀 수 있었다.
오늘의 교훈) 인접행렬을 만들때, 항상 여러개의 간선에 조심하자