-
Notifications
You must be signed in to change notification settings - Fork 0
/
전보.py
38 lines (31 loc) · 799 Bytes
/
전보.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
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m, c = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)
for _ in range(m):
x, y, z = map(int, input().split())
graph[x].append((y, z))
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 i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(c)
count = 0
max_distance = 0
for d in distance:
if d != INF:
count += 1
max_distance = max(max_distance, d)
print(count-1, max_distance)