문제 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을 출력한다.'라는 조건이 있는데, 말이 너무 어렵다. 쉽게 말해서 음수 사이클을 찾으라는 이야기다. 음수 사이클을 체크하는 부분만 넣어주면 문제없이 해결할 수 있..
1. 최단 경로의 이해 먼저 최단 경로의 기본 성질에 대해 파악해보자. u → v : 노드 u에서 노드 v로의 하나의 엣지로 구성된 경로 s ⇝ v : 노드 s에서 v로의 경로를 표 시하고, 중간에 여러 노드가 존재 가능 s ⇝ u → v 인 경우, 이 경로에서 u는 v의 predecessor 또는 parent이다 만약 s ⇝ u → v 가 s에서 v로의 최단 경로 중 하나라면, s ⇝ u 역시 s에서 u까지의 최단 경로 중 하나이다. s에서 v까지의 여러 경로 중에서 u를 통해 v에 도달하는 경로중에 최단 경로가 있다는 의미이고, s ⇝ u를 먼저 계 산하여 알고 있다면, s ⇝ u → v는 쉽게 계산할 수 있다. dist[v] = "s에서 v까지의 최단 경로의 길이"라고 정의하면 다음과 같은 식이 성..
문제 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 백준 1753번 문제인 최단경로 문제와 유사한 문제다. 마찬가지로 다익스트라 알고리즘을 적용하여 해결할 수 있다. 다만, 이 문제 같은 경우 두 정점(v1, v2)을 반드시 거쳐야 한다는 제약조건을 고려해야 한다. 1번 노드부터 출발하여 n번 노드까지 이동하는 경로는 다음과 같이 두 가지로 나뉜다. 1) v1번 노드를 먼저 방문한 후, v2번 노드를 방문하..
