감사합니다.
위의 두, 세번째 TC에서 막힌 분들에게 팁을 드립니다.
Ad Hoc 풀이긴 하지만,
(g, h) 간선에만 아주 작은 값(예 0.01) 을 빼주어서, 동일 비용의 다른 간선을 통하는 경로보다 (g, h) 간선을 통하는 경로를 반드시 채택하도록 하여 parent 추적을 통해 (g, h) 간선을 지나는지 추적하는 방법을 풀 수 있습니다.
9370번 - 미확인 도착지
감사합니다.
위의 두, 세번째 TC에서 막힌 분들에게 팁을 드립니다.
Ad Hoc 풀이긴 하지만,
(g, h) 간선에만 아주 작은 값(예 0.01) 을 빼주어서, 동일 비용의 다른 간선을 통하는 경로보다 (g, h) 간선을 통하는 경로를 반드시 채택하도록 하여 parent 추적을 통해 (g, h) 간선을 지나는지 추적하는 방법을 풀 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
vect_r 4년 전 11
Input
3
5 5 1
1 3 5
1 2 1
2 4 2
2 3 2
3 5 3
4 5 3
5
5 5 1
1 4 5
1 2 1
2 4 2
2 3 2
3 5 3
4 5 3
5
6 7 3
1 4 5
1 2 1
2 4 2
2 3 2
3 5 3
4 5 3
5 6 4
2 6 9
5
3
6
Output
5
5
5 6