CSES PS - investigation (다익스트라, 위상정렬)
https://cses.fi/problemset/task/1202 볼륨이 크다. 사이클이 허용된 가중치가 있는 방향그래프가 주어진다. 시작점 1에서 끝점 n까지 최소 비용으로 이동할 때, (1)그 비용 (2) 가능한 경로의 수, (3) 가능한 경로 중 가장 적은 간선을 지나치는 경우 그 간선의 수, (4) 가장 많은 간선을 지나는 경우 그 간선의 수. (1),(2),(3),(4)를 모두 구하는 문제 (1)은 다익스트라로 풀 수 있고, (2),(3),(4)는 DAG일 때 dp로 풀 수 있는 내용이다. 사이클이 있는 그래프라고 해도 최소비용으로 이동하는 경로는 항상 DAG임이 분명하다. 1. 주어진 그래프에서 유효한 즉, 최소비용 경로에 해당하는 간선들만 남겨서 DAG를 만든다. dist(1~u) + w +..
2020. 1. 29.