FilesExpand file tree

master

/

1916.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (36 loc) · 1.14 KB

master

/

1916.py

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (36 loc) · 1.14 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

43

44

45

46

47

48

49

50

51

52

import sys

import heapq

INF = int(1e9)

# 도시의 개수(n) - 노드

# 버스의 개수(m) - 간선

n = int(input())

m = int(input())

# 버스비용을 거리라고 생각할 것임.

# 최단 거리(최소 비용) 테이블을 INF(10억)으로 초기화

distance = [INF] * (n+1)

graph =[[] for _ in range(n+1)]

# 그래프의 정보를 입력 받음(도시, 버스)

for i in range(1, m+1) :

a, b, c = map(int, sys.stdin.readline().split())

graph[a].append((b,c))

# 출발점(start) - 출발 노드

# 도착점(end) - 도착 노드

start, end = map(int, sys.stdin.readline().split())

# 우선순위 큐를 이용한 개선된 다익스트라 알고리즘

# 시간 복잡도 : O(mlogn)

def dijkstra(start) :

q = []

heapq.heappush(q, (0, start))

distance[start] = 0

while q :

dis, now = heapq.heappop(q)

# 이미 처리된 노드라면 무시

if distance[now] < dis :

continue

for i in graph[now] :

cost = dis + i[1]

if cost < distance[i[0]] :

distance[i[0]] = cost

heapq.heappush(q, (cost, i[0]))

dijkstra(start)

print(distance[end])