Submission #63295833

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque
from heapq import heappush, heappop
n, m, x = map(int, input().split())
G = [[] for i in range(n+1)]
Gr = [[] for i in range(n+1)]
for i in range(m):
  a, b = map(int, input().split())
  G[a].append(b)
  Gr[b].append(a)
queue = []
queue.append((0, 1, False))
queue.append((x, 1, True))
dist = [float("inf")]*(n+1)
dist[1] = 0
distr = [float("inf")]*(n+1)
distr[1] = x
while queue:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque
from heapq import heappush, heappop

n, m, x = map(int, input().split())
G = [[] for i in range(n+1)]
Gr = [[] for i in range(n+1)]

for i in range(m):
  a, b = map(int, input().split())
  G[a].append(b)
  Gr[b].append(a)

queue = []
queue.append((0, 1, False))
queue.append((x, 1, True))
dist = [float("inf")]*(n+1)
dist[1] = 0
distr = [float("inf")]*(n+1)
distr[1] = x

while queue:
  _, v, rev = heappop(queue)
  
  c = min(dist[v]+1, distr[v]+x+1)
  cr = min(dist[v]+x+1, distr[v]+1)
  
  for nei in G[v]:
    if c < dist[nei]:
      dist[nei] = min(dist[nei], c)
      heappush(queue, (c, nei, False))
    
  for nei in Gr[v]:
    if cr < distr[nei]:
      distr[nei] = min(distr[nei], cr)
      heappush(queue, (cr, nei, True))

# print(dist, distr)
print(min(dist[n], distr[n]))  

Submission Info

Judge Result