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: '한 정점'에서 '모든 정점'으로의 최단경로
인접 리스트를 활용하여 연결된 정점들의 정보를 저장해준다. 우선순위 큐를 사용하여 인접 노드들 중 거리가 가까운 노드부터 처리한다. 인접 노드를 거쳐서 가는 거리가 기존 거리보다 짧다면 해당 거리를 최단경로로 설정한다.

  1. i에서 x로의 최단경로
    dijkstra 함수에 i값 (1 ~ n)을 인자로 각각 넣어주며 i에서 모든 정점으로의 최단경로를 dst배열에 넣어준다. 필요한 값은 i에서 x로 가는 거리이므로 n개의 dst[x] 값을 ans 배열에 순서대로 넣어준다.
  2. x에서 i로의 최단경로
    dijkstra 함수에 x값을 인자로 넣어주고 x에서 모든 정점으로의 최단경로를 ans 배열 값에 더해준다.
    ans 배열 중 가장 큰 값을 답으로 출력한다.

[소스코드]


'ALGORITHM > BOJ' 카테고리의 다른 글

[BOJ] 2211번 네트워크 복구 (C++)  (0) 2022.01.17
[BOJ] 13549번 숨바꼭질 3 (C++)  (0) 2022.01.17
[BOJ] 2887번 행성 터널 (C++)  (0) 2022.01.05
[BOJ] 1939번 중량제한 (C++)  (0) 2022.01.05
[BOJ] 3020번 개똥벌레 (C++)  (0) 2022.01.05