acmicpc 1865 썸네일형 리스트형 BOJ #1865 웜홀 문제 링크 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀 www.acmicpc.net 그래프의 경로 상에 음수 간선이 존재하는 벨만포드 알고리즘 입문 문제입니다. 별도의 트릭을 필요로 하지 않으며 벨만포드 알고리즘을 충실히 구현하면 됩니다. 벨만포드 알고리즘의 정의상, 정점의 개수(V) - 1회만큼 경로 갱신을 반복하면 전체 최단 경로들을 모두 구할 수 있습니다. 이후에 한번 더 인접 리스트를 통해 경로 갱신을 했을 때 최단 거리가 갱신되는 경우가 발생한다면, 해당.. 더보기 이전 1 다음