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

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

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.에서의 최단 경로의 합이 됩니다.

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

잘 몰라서 그러는데 정방향 간선에 왜 -1을 곱하는지 알려주실 수 있을까요?