문제

풀이

문제
그래프에 대한 정보가 입력되고
특정 노드 v1과 v2가 입력되는데

이 때 1에서 N번 노드까지 가능경로중 v1과 v2를 모두 거치는 경우를 모두 구해야한다.

그렇다면 경로는 크게 case를 2가지로 나눌 수 있다.
1.
1번 -> v1 -> v2 -> N
2.
1번 -> v2 -> v1 -> N

위 두케이스중 min값을 찾아 출력해주면 문제는 결된다.

그렇다면 한지점에서 다른지점까지의 최단경로가아니라 플로이드 워셜 알고리즘을 사용해 볼 수 있지만
이때 시간복잡도는 O(N^3) (N <= 800) 이에따라
800의 세제곱인 5억이 넘어가는 연산횟수가 걸리므로 1초안에 실행되기는 어려워 보인다.

그렇다면 다익스트라 알고리즘을 이용할 수 있는데
이때는 시간복잡도가 O(E log E)가되고 E의 최대범위는 20만 이므로
20만 log 20만이 되고 대략 2의 10제곱이 1000이라하면 2의 21제곱을 20만쯤으로 볼 수 있고 이때
연산 횟수는
1번에서의 최단거리 테이블
v1번에서의 최단거리 테이블
v2번에서의 최단거리 테이블
총 4번의 테이블을 구해야 하므로

최대 연산횟수는 20만 x 21 x 3 (log20만을 21로 대략함)
그러면 연산횟수가 120만정도로 볼수있고 이는 해볼만한 방법이다.

코드

# input sample
# 4 6
# 1 2 3
# 2 3 3
# 3 4 1
# 1 3 5
# 2 4 5
# 1 4 4
# 2 3

# output sample
# 7
# 입력 : 첫째줄에 정점의 개수 N과 간선의 개수 E가 주어진다.
#       그 다음줄 부터는 u, v, w 인 방향이 없는 간선의 정보가 주어진다.
#       마지막줄에는 1부터 N의 노드를 갈 때 꼭지나쳐야하는 정점
#       v1과 v2가 주어진다.
#       또한 방향성이 없는 그래프이다.


import sys
import heapq


INF = int(1e9)

input = sys.stdin.readline

N, E = map(int, input().split())

graph = [[] for _ in range(N+1)]
distance = [INF] * (N+1)


for _ in range(E):
  u, v, w = map(int, input().split())
  graph[v].append((w,u))
  graph[u].append((w,v))


v1, v2 = map(int, input().split())


def dijakstra(start):
  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0
  while q:
    dis, cur = heapq.heappop(q)

    if(dis > distance[cur]):
      continue

    for j in graph[cur]:
      cost = j[0] + dis
      
      if(cost < distance[j[1]]):
        distance[j[1]] = cost
        heapq.heappush(q,(cost, j[1]))

tmp = INF


        
#case1, case2구하기

distance = [INF] * (N+1)
dijakstra(1)
case1 = distance[v1] 
case2 = distance[v2]

distance = [INF] * (N+1)
dijakstra(v1)
case1 += distance[v2]

distance = [INF] * (N+1)
dijakstra(v2)
case1 += distance[N]
case2 += distance[v1]

distance = [INF] * (N+1)
dijakstra(v1)
case2 += distance[N]



result = min(case1, case2)

if(result >= INF):
  print(-1)
else:
  print(result)