[테스트케이스 추가] 백준 1753 최단경로 (python, 파이썬)

1. 문제

https://www.acmicpc.net/problem/1753

1753번: 최단경로

2. 풀이

전형적인 다익스트라문제.

 

[다익스트라 풀이]

1) dist, gph, edges(heap) 세 가지 list가 필요하다.

dist = [math.inf for i in range(v+2)]
gph = [[] for i in range(v+2)]
edges=[]

2) gph에 연결관계를 넣는다.

gph[u].append((v,w)): u에서 v로 갈 때 w 가중치를 준다

 

3) 시작점의 gph를 dist와 edges에 넣는다.

dist[s]=0
heapq.heappush(edges,(dist[s],s))

4) edges를 pop하면서 새로 본 distance가 기존 dist보다 작다면 업데이트하고 edges에 넣는다.

while edges:
  cost, pos = heapq.heappop(edges) # 순서대로 cost와 pos
  for p, c in gph[pos]: # gph는 p와 c 순서로
    c+=cost # c+=cost 로 cost 계산
    if dist[p]>c:
      dist[p]=c # 업데이트
      heapq.heappush(edges,(c,p))

 

3. 구현

import sys
import heapq
import math

sys.stdin=open("input.txt")

v,e = map(int, sys.stdin.readline().split())
s = int(sys.stdin.readline())

dist = [math.inf for i in range(v+2)]
gph = [[] for i in range(v+2)]
edges=[]

while e:
  e-=1
  u,v,w = map(int, sys.stdin.readline().split())
  gph[u].append((v,w))

dist[s]=0
heapq.heappush(edges,(dist[s],s))
while edges:
  cost, pos = heapq.heappop(edges)
  for p, c in gph[pos]:
    c+=cost
    if dist[p]>c:
      dist[p]=c # 업데이트
      heapq.heappush(edges,(c,p))

for item in dist[1:-1]:
  if item==math.inf:
    print("INF")
  else:
    print(item)

 

4. 추가 테스트케이스

8 12
1
1 8 7 
7 3 2 
7 5 8 
2 8 7 
3 4 8 
2 1 8 
5 1 8 
5 3 2 
1 7 1 
2 6 5 
4 1 8 
7 6 7

답

0
INF
3
11
9
8
1
7

8 20
1
5 8 5 
7 4 5 
4 5 1 
1 7 5 
8 6 1 
5 2 4 
4 7 2 
7 1 5 
4 6 9 
6 5 1 
7 6 1 
7 3 2 
8 5 2 
6 3 1 
8 4 9 
8 3 3 
4 3 3 
8 2 5 
1 4 3 
3 5 8

답

0
8
6
3
4
6
5
9