-
Notifications
You must be signed in to change notification settings - Fork 0
/
q1.py
94 lines (87 loc) · 2.81 KB
/
q1.py
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
# import heapq
# import sys
#
# input = sys.stdin.read
#
#
# def shortest_path():
# # خواندن ورودی
# data = input().split()
# n = int(data[0])
# m = int(data[1])
#
# # ساختن گراف
# graph = [[] for _ in range(n + 1)]
# index = 2
# for _ in range(m):
# u = int(data[index])
# v = int(data[index + 1])
# w = int(data[index + 2])
# graph[u].append((v, w))
# graph[v].append((u, w))
# index += 3
#
# # پیادهسازی الگوریتم دایجسترا
# def dijkstra(start):
# distances = [float('inf')] * (n + 1)
# distances[start] = 0
# priority_queue = [(0, start)]
# while priority_queue:
# current_distance, current_vertex = heapq.heappop(priority_queue)
# if current_distance > distances[current_vertex]:
# continue
# for neighbor, weight in graph[current_vertex]:
# distance = current_distance + weight
# if distance < distances[neighbor]:
# distances[neighbor] = distance
# heapq.heappush(priority_queue, (distance, neighbor))
# return distances
#
# # پیدا کردن کوتاهترین مسیر از راس ۱
# distances = dijkstra(1)
#
# # چاپ خروجی
# for i in range(1, n + 1):
# if distances[i] == float('inf'):
# print(-1)
# else:
# print(distances[i])
#
#
# # فراخوانی تابع
# shortest_path()
import heapq
def shortest_path():
# خواندن ورودی
n, m = map(int, input().split())
# ساختن گراف
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, v, w = map(int, input().split())
graph[u].append((v, w))
graph[v].append((u, w))
# پیادهسازی الگوریتم دایجسترا
def dijkstra(start):
distances = [float('inf')] * (n + 1)
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# پیدا کردن کوتاهترین مسیر از راس ۱
distances = dijkstra(1)
# چاپ خروجی
for i in range(1, n + 1):
if distances[i] == float('inf'):
print(-1)
else:
print(distances[i])
# فراخوانی تابع
shortest_path()