Advertisement
Guest User

Untitled

a guest
Oct 20th, 2019
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.48 KB | None | 0 0
  1. from heapq import *
  2. n, m, k, t = map(int, input().split())
  3. e = [[] for _ in range(n+1)]
  4. for _ in range(n):
  5.     ot, ku, p = map(int, input().split())
  6.     e[ot].append((ku, p))
  7.     e[ku].append((ot, p))
  8. ans = [10**10]*(n+1)
  9. ans[m] = 0
  10. #print(ans)
  11. ch = [(0, m)]
  12. while len(ch) > 0:
  13.     l, curr = heappop(ch)
  14.     for nbr,s in e[curr]:
  15.         if l+s < ans[nbr]:
  16.             ans[nbr] = l+s
  17.             heappush(ch, (l+s, nbr))
  18. print("YES"+" "+str(ans[k]) if ans[k]<= t else "NO")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement