[BOJ]1719번: 택배

문제: https://www.acmicpc.net/problem/1719

---

다익스트라로 해결한 문제입니다.

 

임의의 A->B 두 순서쌍 경로 사이에 가장 먼저 방문하게 되는 노드를 구해야하는 문제입니다.

 

다익스트라를 사용하면 임의의 노드 A에 대해 나머지 노드에 대한 최단 경로 + 방문 정보를 저장할 수 있습니다.

그래서 N 개의 노드에 대해 N번 다익스트라를 돌린 후 1회 다익스트라 수행 때 마다 i번째 노드에서 나머지 노드를 방문할 때 최초로 방문해야 하는 노드 정보를 저장합니다. N번을 모두 돌리게 되면 2차원 배열 정답을 완성할 수 있습니다.

 

N제한이 작으므로 log(V*Elog(V)로도 해결할 수 있습니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1719.java