백준 1504(특정한 최단 경로) - Python
2023. 9. 28. 21:41ㆍ알고리즘(python)/최단경로
접근
특정노드에서 특정노드까지 가는 최단거리가 필요하니 다익스트라 알고리즘을 사용해야함.
시작지점, v1, v2 기준의 거리를 구하고 s + v1 +v2 + t, s+v2+v1+t 까지의 거리를 구한다.
나의 코드
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
n, e = map(int,input().split())
INF = int(1e9)
G = [[] for _ in range(n+1)]
for _ in range(e):
a, b ,c = map(int,input().split())
G[a].append((b,c))
G[b].append((a,c))
def dik(start):
distance = [INF] * (n+1)
V = []
heappush(V,(start,0))
distance[start] = 0
while V:
t,v = heappop(V)
if distance[t] < v:
continue
for t2,v2 in G[t]:
if distance[t2] > v+v2:
distance[t2] = v+v2
heappush(V,(t2,v+v2))
return distance
v1 ,v2 = map(int,input().split())
d1 = dik(1)
dv1 = dik(v1)
dv2 = dik(v2)
r1 = d1[v1]+dv1[v2]+dv2[n]
r2 = d1[v2]+dv2[v1]+dv1[n]
r = min(r1,r2)
if r >= INF:
print(-1)
else:
print(r)
'알고리즘(python) > 최단경로' 카테고리의 다른 글
백준 1916(최소비용 구하기) - python (1) | 2023.10.04 |
---|---|
백준 1865(웜홀) - python (0) | 2023.10.03 |
백준 1753(최단경로) - python (0) | 2023.09.30 |
백준 1238(파티) - python (0) | 2023.09.27 |