https://www.acmicpc.net/problem/1753
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.
www.acmicpc.net
다익스트라 기초인데 너무 오랜만이기도 하고 파이썬으로 작성해서 너무 어렵다...
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
import sys
import heapq
INF = int(1e9)
V, E = map(int, sys.stdin.readline().split())
K = int(sys.stdin.readline())
graph = [[] for _ in range(V + 1)]
distance = [INF] * (V + 1) # 최단거리 테이블
# 간선 정보 저장
for i in range(E):
u, v, w = map(int, sys.stdin.readline().split())
graph[u].append((v, w))
# 다익스트라
def dijkstra(start):
q = []
# 시작 노드 설정, 우선순위 큐 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
# 가장 최단거리가 짧은 노드 꺼내기
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리된 적 있는 노드라면 무시
if distance[now] < dist:
continue
# 현재 노드와 인접 노드 확인
for v in graph[now]:
cost = dist + v[1]
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은경우
if cost < distance[v[0]]:
distance[v[0]] = cost
heapq.heappush(q, (cost, v[0]))
dijkstra(K) # 다익스트라 수행
for i in range(1, V + 1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])
|
cs |