컴공과고씨

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 간단 정리 정점이 주어질 때 시작점이 주어지고 그 시작점으로 부터 각 정점의 최단거리를 출력하는 문제. 문제 해결 방법 다익스트라 알고리즘을 사용하여 쉽게 풀 수 있는 문제이다. 다익스트라를 모른다면 https://hagisilecoding.tistory.com/134 여기서 보고 오시면 쉽게 풀 수 있습니다. 전체 코드 1 2 3 4 5 6 7 8 9 ..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 간단 정리 방향성 없는 그래프 주어짐. 1번 부터 n 정점까지 최단 거리로 이동함. 조건은 임의로 주어진 두 정점은 반드시 통과해야함. 그리고 한 번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이용가능. 1번에서 n정점으로 이동할 때 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 길이를 출력하라 경로가 없으면 -1을 출력. 문제 해..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 간단 정리 여러 도시가 있고 그 도시를 다닐수 있는 여러 버스가 있다. 시작 도시에서 도착 도시까지 비용을 최소로 하는 비용을 구하여라. 문제 해결 방법 다익스트라 알고리즘을 사용하면 풀 수 있는 문제이다. 다익스트라를 모른다면 https://hagisilecoding.tistory.com/134 여기서 한번 어떤 알고리즘인지 보고 오면 어떤 식으로 이 문제..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 활용한 문제로 bfs를 이용해도 가능하지만 시간 측면으로 볼때 다익스트라가 더 빠르고 나중에 다른 문제를 풀 때 다익스트라로 풀지않고 bfs로 풀면 시간 초과가 걸리는 문제들이 많기 때문에 최단 경로 문제 같은 경우 다익스트라로 풀어주는게 좋다. 다익스트라 알고리즘는 https://hagisilecoding.tistory.com/134 여기서 살..