글 읽기 - 9370) 간단한 예제

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

감사합니다.

위의 두, 세번째 TC에서 막힌 분들에게 팁을 드립니다.

Ad Hoc 풀이긴 하지만,

(g, h) 간선에만 아주 작은 값(예 0.01) 을 빼주어서, 동일 비용의 다른 간선을 통하는 경로보다 (g, h) 간선을 통하는 경로를 반드시 채택하도록 하여 parent 추적을 통해 (g, h) 간선을 지나는지 추적하는 방법을 풀 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge