appa   4달 전

문제 하단에 있는 알고리즘 분류에 '밸만 포드'와 'SPFA'가 추가되었으면 합니다.

문제가 특수한 케이스라서 굳이 유량 개념 없이도 해결가능합니다.

혹시 유량 네트워크 없이 어떻게 푸셨는지 알 수 있을까요? 궁금합니다.

소스 코드가 비공개 상태셔서 ㅠㅠ

appa   4달 전

step 1. 1번 정점에서 N번 정점으로 가는 최단 경로를 찾습니다.

step 2. "step 1."에서 구한 최단 경로가 예를 들어 1->a->b->N의 경로였다면 정방향 간선(1->a, a->b, b->N)의 가중치에는 -1을 곱해주고, 역방향 간선(a->1, b->a, N->b)의 가중치는 양의 무한대로 변경을 해줍니다.

step 3. N번 정점에서 1번 정점으로 가는 최단 경로를 찾습니다.

답은 step 1.과 step 3.에서의 최단 경로의 합이 됩니다.

핵심 아이디어를 그림으로 표현하면 다음과 같이 표현할 수 있겠습니다.

7bfc562cbeb95c9c29b3f51e9c40c0de.png


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