목록벨만 포드 (1)

Doby's Lab

[알고리즘] 백준 11657번: 타임머신 (C++), 벨만 포드

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net [벨만 포드 정리] (https://yabmoons.tistory.com/365) 다음 블로그를 통해 정리했다. 1. 모든 간선들을 탐색하면서 간선이 잇는 출발 정점이 '한 번이라도 계산된 정점'이라면 해당 간선이 잇는 정점의 거리를 비교해서 업데이트한다. 2. 1번 과정을 반복한다. [한 번이라도 계산된 정점 == dist의 값이 IN..
PS/BOJ 2021. 12. 9. 02:31
이전 Prev 1 Next 다음