1238번: 파티 www.acmicpc.net 이 문제는 N개의 숫자로 구분된 각각의 마을에 살고 있는 N명의 학생이 X번 마을에 모여서 파티를 벌인 뒤 각자의 마을로 최단 시간에 돌아갈 때, 오고 가는데 가장 오래 걸린 학생을 찾는 문제이다. 단, 주어지는 도로들은 모두 단방향이다. 우선 X번 마을에서 출발해 각자의 마을로 돌아가는데 걸리는 최단 시간을 구해보자. 이는 각 마을을 정점으로 하고 각 도로를 방향이 있는 간선으로 하는 그래프로 해석하면 각 마을까지의 최단 시간은 X번 마을을 시작점으로 하는 dijkstra 알고리즘을 활용해 구할 수 있다. 하지만 각자의 마을에서 X번 마을에 도착하는 최단 시간을 구하기 위해서 위 dijkstra 알고리즘을 바로 적용할 경우 각 마을을 시작점으로 하는 dij..
