백준 1238번. 파티 (Java)

문제 링크 : https://www.acmicpc.net/problem/1238

모든 마을에서 출발하여 X 마을에 들렀다가 다시 돌아오는 길이 가장 큰 값을 구하는 문제입니다.

N이 크지 않아서 플로이드와샬, 다익스트라 어느것으로 해도 풀리는 문제입니다.

하지만 X에 대한 최단 경로만 구하면 되는 상황에서 모든 정점에 대해 다익스트라를 하는 것은 비효율 적입니다.

그래서 'X마을 -> 다른 모든 마을' 의 최단경로와 '다른 모든 마을 -> X마을' 의 최단경로.

단 두번만 다익스트라를 돌려서 문제를 해결할 수 있습니다.

X마을에서의 최단 경로는 시작점을 X로 놓고 하면 되지만

X마을로 향하는 최단 경로는 조금 다릅니다.

입력받는 간선의 값을 전부 뒤집어서 넣은 뒤에 시작점을 X로 하여 구해야 합니다.

인접행렬을 예로 들면 원래는 edge[v1][v2] = cost 이렇게 입력하는 식을 edge[v2][v1] = cost 로 입력한 edge 배열을 이용하여 구할 수 있습니다.

저는 처음부터 인접리스트를 두개 생성하여 구하는 방법으로 하였습니다.