i -> j 를 갈 때,
i -> k -> j 를 가는게 더 짧으면 업데이트 한다.
floyd-warshall 의 아이디어다.
O(V^3)
다음 문제때, 조금 더 자세히 살펴보면서 증명까지 가능하면 해보겠다.
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 백준온라인져지 1613 역사 풀이 (0) | 2018.02.03 |
|---|---|
| BOJ 백준온라인져지 10159 저울 풀이 (0) | 2018.02.01 |
| BOJ 백준온라인져지 11376 열혈강호 2 풀이 (0) | 2018.01.27 |
| BOJ 백준온라인져지 2822 점수 계산 풀이 (0) | 2018.01.25 |
| BOJ 백준온라인져지 11375 열혈강호 풀이 (0) | 2018.01.23 |