특정 최단거리

문제

무방향 그래프가 주어질 때, 정점 1번에서 정점 N번으로 가는 최단거리를 구하려 하는데, 그 과정에서 두 개의 정점을 반드시 거쳐야 한다. 한 번 방문했던 정점을 또 다시 방문하는 것도 허용하고, 간선도 마찬가지로 여러번 방문하는 것을 허용한다고 할 때, 1번에서 N번으로 가는 “특정한" 최단거리를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 4 ≤ N ≤ 1,000, 1 ≤ M ≤ N*(N-1)/2 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b, c로 이루어져 있으며, 이는 정점 a와 정점 b가 가중치 c인 간선으로 연결되어 있다는 의미이다. 마지막 줄에는 반드시 거쳐야 하는 두 정점 A, B가 주어진다. ( 1 ≤ a, b ≤ N, 2 ≤ A, B ≤ N, 1 ≤ c ≤ 50,000, a ≠ b, A ≠ B )

 

출력

1번 정점에서 N번 정점으로 가는 “특정한" 최단거리를 출력한다. 단, “특정한" 최단거리란, 주어진 정점 A와 B를 반드시 방문할 때의 최단거리를 의미한다.

 

예제 입력

4 6

1 2 3

2 3 3

3 4 1

1 3 5

2 4 5

1 4 4

2 3

예제 출력

7

 

#코드

from collections import deque
import sys
 
def dijkstra(graph, start, shortest):
  global N, M
  
  deq = deque()
  deq.append((0, start))
  
  while deq:
    cand_shortest, now = deq.popleft()
    
    if cand_shortest > shortest[now]: continue
    
    for adj in graph[now]:
      cost = cand_shortest + adj[1]
      
      if cost < shortest[adj[0]]:
        shortest[adj[0]] = cost
        deq.append((cost, adj[0]))
      
 
if __name__ == "__main__":
  input = sys.stdin.readline
  INF   = int(1e9)
  
  N, M    = map(int, input().split())
  myGraph = [[] for _ in range(N + 1)]
  
  for _ in range(M):
    a, b, c = map(int, input().split())
    
    myGraph[a].append((b, c))
    myGraph[b].append((a, c))
  
  A, B = map(int, input().split())
  
  res_sum = 0
  # 1. 시작점부터 A, B 각각의 최단거리를 구한다.
  shortest = [INF for _ in range(N + 1)]
  dijkstra(myGraph, 1, shortest) 
  # 2. 더 작게 나온 결과를 첫 번째 방문지로 결정한다.
  # 더 작게 나온 최단거리부터 다음 거점까지 최단 거리를 구한다.
  min_val = 0
  if shortest[A] < shortest[B]: # 시작점 -> A -> B 
    min_val = shortest[A]
    shortest = [INF for _ in range(N + 1)]
    dijkstra(myGraph, A, shortest)
    res_sum += (min_val + shortest[B])
    # 3. 마지막 거점에서 목적지까지의 최단 거리를 구한다.
    shortest = [INF for _ in range(N + 1)]
    dijkstra(myGraph, B, shortest) 
    res_sum += shortest[N]
  else: # 시작점  -> B -> A
    min_val = shortest[B]
    shortest = [INF for _ in range(N + 1)]
    dijkstra(myGraph, B, shortest)
    res_sum += (min_val + shortest[A])
    # 3. 마지막 거점에서 목적지까지의 최단 거리를 구한다.
    shortest = [INF for _ in range(N + 1)]
    dijkstra(myGraph, A, shortest) 
    res_sum += shortest[N]
  
  print(res_sum)

 

# 코드 (개선)

from collections import deque
import sys
 
def dijkstra(graph, start, shortest):
  global N, M
  
  deq = deque()
  deq.append((0, start))
  
  while deq:
    cand_shortest, now = deq.popleft()
    
    if cand_shortest > shortest[now]: continue
    
    for adj in graph[now]:
      cost = cand_shortest + adj[1]
      
      if cost < shortest[adj[0]]:
        shortest[adj[0]] = cost
        deq.append((cost, adj[0]))
      
 
if __name__ == "__main__":
  input = sys.stdin.readline
  INF   = int(1e9)
  
  N, M    = map(int, input().split())
  myGraph = [[] for _ in range(N + 1)]
  
  for _ in range(M):
    a, b, c = map(int, input().split())
    
    myGraph[a].append((b, c))
    myGraph[b].append((a, c))
  
  A, B = map(int, input().split())
  
  res_a_sum = 0
  res_b_sum = 0
  # 1. 시작점부터 A, B 각각의 최단거리를 구한다.
  shortest_origin = [INF for _ in range(N + 1)]
  dijkstra(myGraph, 1, shortest_origin) 
  
  # 2. 더 작게 나온 결과를 첫 번째 방문지로 결정한다.
  #################################################################################
  min_val = 0
  min_val = shortest_origin[A]
  shortest = [INF for _ in range(N + 1)]
  dijkstra(myGraph, A, shortest)
  res_a_sum += (min_val + shortest[B])
  # 3. 마지막 거점에서 목적지까지의 최단 거리를 구한다.
  shortest = [INF for _ in range(N + 1)]
  dijkstra(myGraph, B, shortest) 
  res_a_sum += shortest[N]
  #################################################################################
  min_val = 0
  min_val = shortest_origin[B]
  shortest = [INF for _ in range(N + 1)]
  dijkstra(myGraph, B, shortest)
  res_b_sum += (min_val + shortest[A])
  # 3. 마지막 거점에서 목적지까지의 최단 거리를 구한다.
  shortest = [INF for _ in range(N + 1)]
  dijkstra(myGraph, A, shortest) 
  res_b_sum += shortest[N]
  #################################################################################
  print(min(res_a_sum, res_b_sum))