알고리즘

목차 문제 링크 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 분류 데이크스트라, 그래프 이론 문제 설명 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 ..

문제가 긴 시뮬레이션 문제다. 문제 내 주의해야 할 부분은 대기열에서 창구로 이동하는 여러개의 우선순위다. - 접수 창구의 우선순위 ① 여러 고객이 기다리고 있는 경우 고객번호가 낮은 순서대로 우선 접수한다. ② 빈 창구가 여러 곳인 경우 접수 창구번호가 작은 곳으로 간다. - 정비 창구의 우선순위 ① 먼저 기다리는 고객이 우선한다. ② 두 명 이상의 고객들이 접수 창구에서 동시에 접수를 완료하고 정비 창구로 이동한 경우, 이용했던 접수 창구번호가 작은 고객이 우선한다. ③ 빈 창구가 여러 곳인 경우 정비 창구번호가 작은 곳으로 간다. 위 내용을 고려해서 처음부터 우선순위 큐를 사용해 문제 풀이를 시작했다. 접수 창구에서는 고객 번호 하나만 고려해도 되지만, 정비 창구에서 여러개의 우선순위가 필요해 Co..