[백준/BOJ] 백준 5542번 : JOI 국가의 행사

https://www.acmicpc.net/problem/5542 5542번: JOI 국가의 행사 예제 1. 3에서 4로 가는 경우는 3-5-4로 이동하면 가장 가까운 축제가 6번이고 거리는 7이다. 이 값이 최대이고, 5에서 2로 가는 경우는 5-3-2, 5-4-2 모두 1번 축제와 거리 5가 되므로 이 값을 출력한다. www.acmicpc.net 우선 축제로부터 각 정점까지 최단거리를 저장해 두고, 해당 값을 기반으로 각 간선들을 축제와 가장 먼 순으로 정렬을 한 뒤, 해당 순서로 간선을 그래프에 붙여 나가면서 유니온 파인드를 통해 같은 그룹의 정점은 묶어 나아간다. 같은 그룹으로 묶어 나아가다가 같은 그룹 내에 출발지와 도착점인 사람이 발견되면, 해당 사람의 축제로부터 가장 먼 길이는 방금 붙여지는..

2023.10.18