다익스트라 돌리면 최단경로DAG를 만들 수 있다.

최단경로 DAG로 풀 수 있어보이는 문제들
5719 거의 최단경로
5822 악어의 지하도시 (이거는 좀 다른 느낌이다. Harry the hamster 풀이 이해하면 쉬움. 역방향 최단경로DAG에서 dp하는 느낌?)
9370 미확인 도착지
2211 네트워크 복구
이외에도 다양한 문제에 응용할 수 있는 강력한 도구

사용완료