https://www.acmicpc.net/problem/6135
접근법
- 플로이드-워셜처럼 풀 수 있다.
- j를 중간점으로 할 때 max(d[i][j], d[j][k])가 d[i][k]가 될 수 있다.
- 기존에 d[i][k]가 있다면 그 값과 비교해서 작은 값을 취한다.
- 1 ~ N의 점에 대해 중간점으로 체크
후기
- 양방향인줄 알고, MST로 접근했었음
- 단방향일때 정렬 후 작은 거리부터 그래프를 구성하고 DFS로 값을 찾았지만 실패(stack 메모리 초과)
- prim 알고리즘처럼 접근...가장 작은 간선부터 처리하면서 기존의 값과 비교해서 큰값으로 업데이트하고.......... ==> 복잡한 아이디어
newbieski