산책 (large)
시간 제한2초메모리 제한1024 MB
S에서 E로 가는 최단 경로 중 사전순으로 가장 앞선 것을 택하고, 그 경로의 정점을 피해 E에서 S로 돌아오는 최단 경로를 구해 두 거리의 합을 출력한다.
문제
코로나 때문에 확찐자가 되어 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다.
현재 있는 곳 에서 출발하여 와 다른 곳인 를 찍고 다시 로 돌아오는 경로를 만들려고 한다. 산책할 때 이미 갔던 정점을 또 가기 싫어 에서 로 올 때는 에서 로 가는 도중에 방문한 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리가 긴 것을 싫어하여 에서 로 가는 가장 짧은 거리와 에서 로 가는 가장 짧은 거리를 원한다.
정점 에서 정점 로 이동할 때, 가장 짧은 거리의 경로가 여러 개 나올 수 있다. 그중 정점 에서 정점 로 이동한 경로를 나열했을 때 사전순으로 가장 먼저 오는 것을 선택한다.
예를 들어, 정점 1에서 정점 2로 이동한다고 했을 때, 가장 짧은 거리의 경로가 1 4 3 2와 1 3 4 2가 있다고 가정해 보자. 두 경로 중 사전순으로 먼저 오는 것은 1 3 4 2이므로 정점 1에서 정점 2로 가는 최단 경로 중 두 번째 것을 선택한다.
이와 같이 산책 경로를 정할 때, 산책 전체 경로의 거리(에서 로 가는 거리 + 에서 로 가는 거리)를 구해보자.
입력
첫 번째 줄에는 정점의 개수 과 두 정점 사이를 잇는 도로의 개수 이 공백으로 구분되어 주어진다.
두 번째 줄부터 번째 줄까지 정점 , 와 정점 에서 정점 로 가는 거리 가 공백으로 구분되어 주어진다. 이때, 정점 와 정점 는 양방향으로 이동해도 된다.
정점 와 정점 를 잇는 도로는 두 개 이상 주어지지 않는다.
번째 줄에는 정점 와 정점 가 공백으로 구분되어 주어진다.
출력
산책의 전체 경로의 길이를 출력한다.
제한
- 는 정수
- 정점의 번호는 부터 시작한다.
- 산책을 할 수 있는 경로가 있는 데이터만 주어진다.