[BOJ]14588번: Line Friends (Small)

 

www.acmicpc.net/problem/14588

---

임의의 두 정점간의 거리를 한 번에 알려줘야 하므로 플로이드로 해결하는 게 적절합니다. 

 

플로이드 노드의 갱신을 위한 점화식은 다음과 같습니다.

 

if (dist[i][j] > dist[i][mid] + dist[mid][j])
  dist[i][j] = dist[i][mid] + dist[mid][j]

 

---

코드(python): github.com/cotchan/algorithm/blob/main/python/BOJ/BOJ14588.py

코드(JAVA): github.com/cottory/algorithm/blob/master/BOJ/BOJ14588.java