1. 문제 설명

산책

2. 문제 분석

다익스트라를 두 번 사용해서 특정 노드 간의 경로 중 첫 번째 최단 경로에 사용된 노드를 제외한 새로운 최단 거리를 구할 수 있다. 이때 주의해야 하는 점은 s ~ e의 이동 시에 먼저 선택되는 최단 경로가 알파벳 순서이기 때문에, 같은 거리라도 이 과정에 따라 두 번째 최단 경로 값이 달라진다는 점이다.

• distances에 기록된 최단 경로 속성을 이용, 시작지에서 도착지까지 커서를 통해 이동하면서 알파벳 순서의 최초 경로를 리턴하자.

3. 나의 풀이

import sys
import heapq
from collections import deque

INF = sys.maxsize
n, m = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    nodes[a].append([b, c])
    nodes[b].append([a, c])
s, e = map(int, sys.stdin.readline().rstrip().split())
for i in range(n+1): nodes[i].sort()
# 연결 그래프 세팅 -> DFS 탐색 위한 노드 순서 변경

def Dijkstra(visited, start):
    distances = [INF for _ in range(n+1)]
    distances[start] = 0
    pq = []
    heapq.heappush(pq, [0, start])

    while pq:
        cur_cost, cur_node = heapq.heappop(pq)
        if distances[cur_node] < cur_cost: continue

        for next_node, next_cost in nodes[cur_node]:
            if next_node in visited: continue
            # 이미 산책한 경로 제외
            if distances[next_node] > next_cost + cur_cost:
                distances[next_node] = next_cost + cur_cost
                heapq.heappush(pq, [next_cost + cur_cost, next_node])

    return distances

distances = Dijkstra(set(), e)
first_cost = 0
cursor = s
visited = set()
while cursor != e:
    for  next_node, next_cost in nodes[cursor]:
        if first_cost + next_cost + distances[next_node] == distances[s]:
            first_cost += next_cost
            visited.add(next_node)
            cursor = next_node
            break
            # 알파벳 순서대로 탐색 -> 한 번 최단 경로 중 입력되면 곧바로 이동, visted에 기록

visited.remove(e)
# s/e는 재방문해야 함
distances = Dijkstra(visited, s)
print(first_cost + distances[e])