64 lines
1.6 KiB
Python
64 lines
1.6 KiB
Python
# 특정한 최단 경로
|
|
|
|
import sys
|
|
import heapq
|
|
|
|
input = sys.stdin.readline
|
|
|
|
def get_short(start, g, n):
|
|
dp = [float('inf')] * (n+1)
|
|
pq = [(0, start)]
|
|
|
|
dp[start] = 0
|
|
while pq:
|
|
dist, now = heapq.heappop(pq)
|
|
|
|
if dist > dp[now]:
|
|
continue
|
|
|
|
for nxt, v in g[now]:
|
|
nxt_dist = dist + v
|
|
if nxt_dist < dp[nxt]:
|
|
dp[nxt] = nxt_dist
|
|
heapq.heappush(pq, (nxt_dist, nxt))
|
|
|
|
return dp
|
|
|
|
def solution():
|
|
n, e = map(int, input().rstrip().split())
|
|
|
|
g = {i: [] for i in range(1, n+1)}
|
|
for i in range(e):
|
|
a, b, c = map(int, input().rstrip().split())
|
|
g[a].append((b,c))
|
|
g[b].append((a,c))
|
|
|
|
v1, v2 = map(int, input().rstrip().split())
|
|
|
|
start_1 = get_short(1, g, n)
|
|
start_v1 = get_short(v1, g, n)
|
|
start_v2 = get_short(v2, g, n)
|
|
|
|
result = min(start_1[v1] + start_v1[v2] + start_v2[n], start_1[v2] + start_v2[v1] + start_v1[n])
|
|
|
|
if result == float('inf'):
|
|
result = -1
|
|
|
|
print(result)
|
|
|
|
return
|
|
|
|
|
|
solution()
|
|
|
|
"""
|
|
걸린 시간: 35분
|
|
|
|
시간 복잡도: 간선에 연결된 각 정점에 대해 모든 연결된 선을 확인하기 때문에 그냥 간선의 길이만큼 본다고 생각하면 된다.
|
|
이때, 간선 하나를 보고 heap 조작을 한번 하기 때문이 loge이다.
|
|
따라서 전체 시간복잡도는 O(eloge)이다.
|
|
|
|
해설: 1 -> v1 -> v2 -> n, 1 -> v2 -> v1 -> n 중 더 짧은 것을 구하면 된다.
|
|
1, v1, v2 기준으로 다 구하면 된다.
|
|
다익스트라는 하던대로 구현하면 완료.
|
|
""" |