필수 정점을 지나는 최단 경로
면접 대비시간 제한1초메모리 제한256 MB
가중치가 있는 무방향 그래프에서 정점 1부터 N까지 가는 경로 중 두 특정 정점을 모두 지나야 하는 최단 거리를 구합니다.
문제
방향이 없는 가중 그래프가 주어진다. 1번 정점에서 N번 정점으로 이동할 때, 서로 다른 두 정점 v1과 v2를 모두 반드시 지나는 경로 중 거리의 합이 가장 작은 경로를 구하라.
정점과 간선은 여러 번 지나도 된다. 단, 조건을 만족하는 경로 중 전체 이동 거리는 최소여야 한다.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000)
다음 E개의 줄에는 세 정수 a, b, c가 주어진다. 이는 a번 정점과 b번 정점 사이에 거리 c인 양방향 간선이 있음을 뜻한다. (1 ≤ c ≤ 1,000)
마지막 줄에는 반드시 지나야 하는 서로 다른 두 정점 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)
임의의 두 정점 사이에 존재하는 간선은 최대 1개이다.
출력
두 필수 정점을 모두 지나 1번 정점에서 N번 정점으로 가는 최단 경로의 길이를 출력한다. 그런 경로가 없으면 -1을 출력한다.