기록방

👉 문제링크 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 🔸 문제 분석 🔸 N명의 사람과 M개의 도로가 있다. X번 사람의 집에 모두가 최단거리로 모이고 집에 갈 때, 소요시간의 최대 값을 출력한다. 각 집 사이의 도로는 단방향 연결이다. 최단거리를 구하고 그 중 최대 값을 찾아야 한다. 각자 집에서 파티로 갈 때는 각각의 최단 거리를 구해야 하므로, 다익스트라 알고리즘을 N-1번 반복한다. 파티에서 집으로 돌아갈 때는 시작 노드에서 다른 모든 노드로의 최단 거리를 구해야 하..

👉 문제링크 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시가 있고, M개의 버스가 있다. M개의 버스는 한 도시에서 다른 도시까지 드는 버스 비용이 있다. 출발 도시부터 도착지 도시까지 버스 비용의 최소 값을 출력한다. 전형적인 다익스트라 알고리즘 문제이다. 그래프에서 한 정점에서 특정 정점까지의 최소비용을 구해야 한다. M개의 버스는 단방향 연결을 나타낸다. 목적지가 나올 때 까지, 각 정점의 최단 거리를 갱신해간다. 목적지에 방문하면 그때의..