글 읽기 - 힌트 좀 주세요..

질문 글 보니까 mcmf 로 풀라고 하던데..

제가 아직 mcmf 를 공부하지 않았거든요.

이 문제가 다익스트라 알고리즘에 포함되어 있는걸로 봐서는

다익스트라로 풀 수 있는 방법이 존재하는 것 같은데..

혹시 그런 풀이법이 있을까요?

혼자 생각해본 방법으로는..

두 가지 방향으로 동시에 다익스트라를 진행시키면서, 방문한 정점을 체크해주고 , 체크된 정점은 방문하지 않으면서

최단거리로 이동한다? 이런식으로 풀려고 하는데 맞는지도 잘 모르겠구요..

힌트가 있을까요???ㅜㅜ

다익스트라로 풀 수 있지만, 별로 간단하진 않고 결국 MCMF의 축소판이라고 볼 수도 있습니다.

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

Baekjoon Online Judge