이 문제를 봤을 때, 플로이드 와샬로 풀 수 있을까 고민했지만 tc의 개수가 5개, N의 크기가 500인 것을 보고 플로이드와 샬을 포기하고, 음의 가중치라는 점에서 벨만 포드 알고리즘을 시도했다. 벨만 포드 알고리즘이 익숙지 않아 많이 헤맸던 문제이지만, 이 문제 덕에 벨만 포드 알고리즘을 한번 더 정리할 수 있었다. 벨만 포드 알고리즘은 다익스트라와 같이 최단 경로 문제를 푸는 알고리즘이지만, 차이점은 변과 변 사이에서 음의 가중치를 가질 수 있다는 점이고 바로 이 점이 훨씬 더 빠른 다익스트라보다 벨만 포드 알고리즘을 사용하는 이유이다. 왜 다익스트라는 음의 가중치를 가지지 못할까? 음의 가중치가 있는 경우 음의 순환(계속 가중치가 최솟값으로 갱신되는 경우)이 있다. 다익스트라는 가중치의 합을 최솟..
