ALGORITHM/BOJ
[BOJ] 1238번 파티 (C++)
yegyeom
2022. 1. 17. 17:35
문제 (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
N개의 마을에는 각각 한 명의 학생이 살고 있고, 입력받은 X번 마을에서 파티가 열린다. 모든 학생들의 이동거리는 최단거리여야 한다.
N명의 학생들 중 (i번째 마을 -> x번 마을) + (x번 마을 -> i번째 마을) 시간이 가장 긴 학생의 소요시간을 출력하면 된다.
Dijkstra Algorithm: '한 정점'에서 '모든 정점'으로의 최단경로
인접 리스트를 활용하여 연결된 정점들의 정보를 저장해준다. 우선순위 큐를 사용하여 인접 노드들 중 거리가 가까운 노드부터 처리한다. 인접 노드를 거쳐서 가는 거리가 기존 거리보다 짧다면 해당 거리를 최단경로로 설정한다.
- i에서 x로의 최단경로
dijkstra 함수에 i값 (1 ~ n)을 인자로 각각 넣어주며 i에서 모든 정점으로의 최단경로를 dst배열에 넣어준다. 필요한 값은 i에서 x로 가는 거리이므로 n개의 dst[x] 값을 ans 배열에 순서대로 넣어준다. - x에서 i로의 최단경로
dijkstra 함수에 x값을 인자로 넣어주고 x에서 모든 정점으로의 최단경로를 ans 배열 값에 더해준다.
ans 배열 중 가장 큰 값을 답으로 출력한다.
[소스코드]
