CheerUp_Cheers

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 #특징 1. 음수 가중치가 존재하는 모든 정점에서의 최단 경로를 알 수 있음. 2. 시간복잡도 O(VE) 정점이 V, 간선이 E라고 했을 때 V-1번 간선들을 모두 돌아봄. 3. 음의 가중치를 가지기 때문에, 음의 사이클을 조심해야함. ->V번째 간선들을 돌아봤을 때, 가중치가 수정이되면 음의 싸이클이 존재. #다익스트라랑 vs 벨만포드..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 www.acmicpc.net #특징 1. DP를 통해서 최소거리를 갱신. 2. 모든 정점에서의 최단 경로를 알 수 있음. 3. 시간복잡도 O(N^3) for문이 ..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.