벨만–포드1 [백준] 11657: 타임머신 - JAVA https://www.acmicpc.net/problem/11657 풀이도시마다 연결된 줄이 있고, 줄마다 가중치가 있다. 가중치에는 음수값도 있어서 1번도시에서 어떤 도시로 가는 과정에서 무한히 오래 전으로 돌릴 수 있으면 -1을 출력해야한다. 그렇지 않다면 2번~n번 도시까지 가는 가장 빠른 시간을 출력한다. 음수 가중치가 있기 때문에 벨만포드 알고리즘을 사용하는 문제였다. 벨만포드 알고리즘에서는 우선 `정점의 개수 - 1`만큼 루프를 돈다. 먼저 정점의 사이즈만큼 dist 배열을 만들어 출발지를 0으로 설정하고 나머지 값은 INF로 설정한다. `정점의 개수 - 1`만큼 루프를 돌면서 dist의 값이 INF가 아닌 정점에 대해 연결 된 정점까지 걸리는 cost를 최솟값으로 갱신한다. `정점의 개수 -.. 2024. 5. 19. 이전 1 다음