exqt   3년 전

4
3 100 2 2 3
4 14 1 4
1 8 1 2
1 2 1 3

입력이 위와 같다면 답은 16입니다.

1번을 약한 충격으로 (총 비용: 3, 작동중: 2, 3)

2번을 약한 충격으로 (총 비용: 3+4, 작동중: 3, 4)

4번을 강한 충격으로  (총 비용: 7+2, 작동중: 3)

3번을 약한 충격으로 (총 비용: 9+1, 작동중: 2) 

2번을 약한 충격으로 (총 비용: 10+4, 작동중: 4)

4번을 강한 충격으로 (총 비용: 14+2, 작동중: x)

dfs로 했을 때 1, 2, 4, 3, 순으로 방문하면 3번의 비용이 8로 계산됩니다.

하지만 위에서 나와있는 것처럼  3->4->2로 하면 비용이 7입니다.

풀이의 힌트는..

문제의 태그 보시면 생각치도 못한 태그가 하나 있습니다.

태그를 보시고도 떠오르지 않으시다면 해당 태그와

https://www.acmicpc.net/proble...

이 문제를 적절히 조합해보시면 도움이 될 것 같습니다.

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