programmer life guidance 101

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 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 29363 3899 2430 18.753% 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양..

> 벨만포드 알고리즘 이어서 소개해드릴 것은 또다른 최단경로 알고리즘입니다. 벨만 포드 알고리즘(Bellman-Ford algorithm)인데요, 알고리즘을 개발한 두 학자의 성을 따서 붙인 이름이라고 합니다. 동시에 독자적으로 알고리즘을 개발했던 또다른 학자의 이름까지 붙여서 벨만 포드 무어 알고리즘이라 명명할 때도 있다는군요. 다익스트라 알고리즘과 마찬가지로 시작점을 정해 주면 다른 모든 정점으로의 최단 경로를 구하는데, 다익스트라 알고리즘보다는 시간이 오래 걸려서 O(VE)의 시간이 걸리지만 이 알고리즘은 간선 cost가 음수일 때도 사용할 수가 있습니다!! 아니 도대체 거리가 음수라니 무슨 소리냐, 뭐 그런 거 다 떼어놓고 그냥 최단거리가 정말 작으면 작을수록 좋다고 친다면, 설령 그게 음수가 되..