Problem:
Single Source Shortest Path For a given weighted graph G(V, E) and a source r , find the source shortest path to each vertex from the source (SSSP: Single Source Shortest Path). Input An edge-weighted graph G ( V , E ) and the source r . | V | | E | r  s 0  t 0  d 0  s 1  t 1  d 1 : s |E|-1  t |E|-1  d |E|-1   |V| is the number of vertices and |E| is the number of edges in G . The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the source of the graph.  s i and t i represent source and target vertices of i -th edge (directed) and d i represents the cost of the i -th edge. Output Print the costs of SSSP in the following format.  c 0  c 1 : c |V|-1  The output consists of |V| lines. Print the cost of the shortest path from the source r to each vertex 0, 1, ... |V|-1 in order. If there is no path from the source to a vertex, print INF . Constraints  1 ≤ |V| ≤ 100000  0 ≤ d i ≤ 10000  0 ≤ |E| ≤ 500000  There are no parallel edges  There are no self-loops  Sample Input 1 4 5 0
0 1 1
0 2 4
1 2 2
2 3 1
1 3 5 Sample Output 1 0
1
3
4 Sample Input 2 4 6 1
0 1 1
0 2 4
2 0 1
1 2 2
3 1 1
3 2 5 Sample Output 2 3
0
2
INF

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




V, E, r = map(int, input().split())

adj = [[] for _ in range(V)]
for i in range(E):
    s, t, d = map(int, input().split())
    adj[s].append((d, t))

n = V
import heapq

INF = float("INF")
dist = [INF for _ in range(n)]
visited = [False for _ in range(n)] 

q = [(0, r)]
dist[r] = 0
path = [0 for _ in range(n)]
def dijkstra():
    while len(q) > 0:
        v = heapq.heappop(q)
        a = v[1]
        if visited[a]:
            continue
        visited[a] = True
        for u in adj[a]:
            w = u[0]
            b = u[1]
            if dist[a] + w < dist[b]: 
                dist[b] = dist[a] + w
                heapq.heappush(q, (dist[b], b))

dijkstra()
for i in range(V):
    if dist[i] == float("inf"):
        print("INF")
    else:
        print(dist[i])

Solution (Python):
v_num, e_num, r = map(int, input().split())
INF = (10000 + 1) * v_num
dist = [INF] * v_num
G = [[] for _ in range(v_num)]
for _ in range(e_num):
    s, t, d = tuple(map(int, input().split()))
    G[s].append((t, d))

from heapq import heappush, heappop
q = []
heappush(q, (0, r))
dist[r] = 0
while q:
    d, node = heappop(q)
    for to, cost in G[node]:
        if dist[to] > d + cost:
            dist[to] = d + cost
            heappush(q, (d+cost, to))

for d in dist:
    if d == INF:
        print('INF')
    else:
        print(d)

Solution (Python):
V,E,r=map(int,input().split())
W=[tuple(map(int,input().split())) for _ in range(E)]
dis=[float('inf')]*V
dis[r]=0
for _ in range(V-1):
    update=False
    for s,t,d in W:
        if dis[t] > dis[s] + d:
            dis[t] = dis[s] + d
            update = True
    if not update: break
for i in dis:
    print(i if i!=float('inf') else 'INF')

Solution (Python):
import heapq
INF = float('inf')

def dijkstra(g, s):
    n = len(g)
    dist = [INF] * n
    dist[s] = 0
    hq = []
    heapq.heappush(hq, (dist[s], s))
    while hq:
        cost, u = heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v, c in g[u]:
            if dist[v] <= dist[u] + c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq, (dist[v], v))
    return dist

V, E, r = map(int, input().split())
g = [[] for _ in range(V)]

for i in range(E):
    s,t,d = map(int, input().split())
    g[s].append((t, d))
    

res = dijkstra(g, r)
for i in res:
    print('INF' if i == INF else i)

Solution (Python):
import heapq

V, E, r = map(int, input().split())
G = [[] for i in range(V)]
for i in range(E):
    s, t, d = map(int, input().split())
    G[s].append([d, t])

INF = 1000000007
mn = [INF] * V
todo = [[0, r]]
fin = [0] * V
heapq.heapify(todo)
while(todo != []):
    v = heapq.heappop(todo)
    if not fin[v[1]]:
        mn[v[1]] = v[0]
        fin[v[1]] = 1
        for i in G[v[1]]:
            if mn[v[1]]+i[0] < mn[i[1]]:
                heapq.heappush(todo, [mn[v[1]]+i[0], i[1]])

for i in range(V):
    print(mn[i] if mn[i] != INF else 'INF')

Solution (Python):
from heapq import *
import sys
input = sys.stdin.readline
INF = 10 ** 18                                          

def dijkstra(V, E, G, s):                               
    d = [INF]*V                                         
    d[s] = 0                                            
    next_set = [(0, s)]                                 
                                                        
                                                        
    while next_set:
        dist, p = heappop(next_set)                     
        if d[p] < dist:
            continue
        for q, cost in G[p]:                            
            temp_d = dist + cost                        
            if temp_d < d[q]:                           
                d[q] = temp_d
                heappush(next_set, (temp_d, q))         
    return d



V, E, s = map(int, input().split())
G = [[] for _ in range(V)]
for _ in range(E):
    p,q,dist = map(int, input().split())
    
    

    G[p].append((q, dist))                            
    

for dist in dijkstra(V,E,G,s):
    if dist == INF:
        print("INF")
    else:
        print(dist)

Solution (Python):
import heapq
N, M, S = map(int, input().split())
edges = [[]for _ in range(N)]
inf = 10**18
for _ in range(M):
    u, v, d = map(int, input().split())
    edges[u].append((v, d))


def dijkstra(s):

    dist = [inf]*N
    dist[s] = 0
    vs = []
    heapq.heappush(vs, (0, s))
    while len(vs):
        res, v = heapq.heappop(vs)
        if res > dist[v]:
            continue
        for nxt, cost in edges[v]:
            if res+cost < dist[nxt]:
                dist[nxt] = res+cost
                heapq.heappush(vs, (dist[nxt], nxt))
    return dist


dist = dijkstra(S)
for i in range(N):
    if dist[i] == inf:
        print("INF")
    else:
        print(dist[i])

Solution (Python):
from heapq import heappush, heappop

v,e,r = map(int,input().split())

edge = [[] for _ in range(v)]

for _ in range(e):
    s,t,d = map(int,input().split())
    edge[s].append((t, d))

cost = [float('inf')]*v
cost[r] = 0

q = [(r, 0)]
while q:
    now, distance = heappop(q)
    
    
    for nxt, newcost in edge[now]:
        if distance + newcost < cost[nxt] :
            cost[nxt] = distance + newcost
            heappush(q, (nxt, distance + newcost))

for i in range(v):
    if cost[i] == float('inf'):
        print('INF')
    else:
        print(cost[i])

Solution (Python):
INF=-10000000000

def bellman_ford(s,D,G):
    D[s]=0
    while True:
        update=False
        for i in range(E):
            e=G[i]
            if D[e[0]]!=INF and (D[e[1]]==INF or D[e[1]]>D[e[0]]+e[2]):
                D[e[1]]=D[e[0]]+e[2]
                update=True
        if not update:
            break

if __name__=="__main__":
    V,E,r=map(int,input().split())
    D=[INF]*V
    G=[]

    for i in range(E):
        G.append(list(map(int,input().split())))
    
    bellman_ford(r,D,G)

    for i in range(V):
        print("INF" if D[i]==INF else D[i])

Solution (Python):
from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline
V, E, r = map(int, input().split())
G = [[] for _ in [0]*V]
for _ in [0]*E:
    a, b, c = map(int, input().split())
    G[a].append((b, c))

INF = 1 << 30
D = [INF]*V
used = [0]*V
q = []
heappush(q, (0, r))

while q:
    d, v = heappop(q)
    if used[v]:
        continue
    used[v] = 1
    D[v] = d
    for u, c in G[v]:
        if used[u]:
            continue
        if d+c < D[u]:
            heappush(q, (d+c, u))

for i in range(V):
    print(D[i] if D[i] != INF else 'INF')

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from collections import defaultdict

def resolve():
    it = map(int, sys.stdin.read().split())
    V, E, r = next(it), next(it), next(it)

    inf = float("inf")

    dp = [inf] * V
    dp[r] = 0

    dx = defaultdict(list)
    for si, ti, di in zip(it, it, it):
        dx[si].append((ti, di))

    sx, tx = {r,}, set()
    while sx:
        for si in sx:
            for ti, di in dx[si]:
                d1 = dp[ti]
                d2 = dp[si] + di
                if d1 > d2:
                    dp[ti] = d2
                    tx.add(ti)
        sx, tx = tx, set()

    ans = []
    print(*["INF" if x == inf else x for x in dp], sep="\n")



if __name__ == "__main__":
    resolve()

Solution (Python):
import heapq

v, e, r = map(int, input().split()) 
edges = [[] for _ in range(v)] 
for i in range(e):
    s, t, d = map(int, input().split())
    edges[s].append([t,d])

def dijkstra(edges, start, num_v):
    dist = [float('INF')]*num_v 
    dist[start] = 0 
    q = []
    heapq.heappush(q, [0,start])
    
    while q:
        _, u = heapq.heappop(q)
        for i in edges[u]:
            if dist[i[0]] > dist[u] + i[1]:
                dist[i[0]] = dist[u] + i[1]
                heapq.heappush(q, [dist[u] + i[1], i[0]])
    return dist

res = dijkstra(edges, r, v)
for i in range(v):
    if res[i] == float('inf'):
        print('INF')
    else:
        print(res[i])

Solution (Python):
import heapq

class Node():
    def __init__(self, id, w):
        self.id = id
        self.weight = w

    def __str__(self):
        return "id: {}\t weight:{}".format(self.id, self.weight)

    def __lt__(self, other):
        return self.weight < other.weight

class WeightDirectedGraph():    
    def __init__(self, V):
        self.G = {i: [] for i in range(V)}
        self.V = V
        self.INF = 10**10

    def append(self, a, b, w):
        self.G[a].append(Node(b, w))

    def dijkstra(self, s):
        
        D = [self.INF] * self.V
        D[s] = 0

        
        H = []
        heapq.heappush(H, Node(s, D[s]))

        while len(H) > 0:
            u = heapq.heappop(H)
            if D[u.id] >= u.weight:
                
                for v in self.G[u.id]:
                    w = u.weight + v.weight
                    if D[v.id] > w:
                        D[v.id] = w
                        heapq.heappush(H, Node(v.id, D[v.id]))
        return D


V,E,r = map(int, raw_input().split())
G = WeightDirectedGraph(V)
for i in range(E):
    s,t,d = map(int, raw_input().split())
    G.append(s,t,d)

for d in G.dijkstra(r):
    if d == G.INF:
        print "INF"
    else:
        print d

Solution (Python):
import heapq
def solve(V,E,r,adjlist):
    cost=[float('inf')]*V
    used=[False]*V
    cost[r]=0
    used[r]=True
    h=[]
    for v in adjlist[r]:
        heapq.heappush(h,v)
    while(len(h)>0):
        u=heapq.heappop(h)
        if used[u[1]]:
            continue
        used[u[1]]=True
        cost[u[1]]=u[0]
        for d,t in adjlist[u[1]]:
            if cost[t]>u[0]+d:
                cost[t]=u[0]+d
                heapq.heappush(h,tuple((cost[t],t)))
    return cost





V,E,r=map(int,input().split())
adjlist=[[] for _ in range(V)]
for _ in range(E):
    s,t,d=map(int,input().split())
    adjlist[s].append(tuple((d,t)))
ans=solve(V,E,r,adjlist)
for i in range(V):
    if ans[i]==float('inf'):
        print("INF")
    else:
        print(ans[i])

Solution (Python):
import heapq

N, M, r = map(int, input().split())
inf = 10 ** 18

def dijkstra(start):
    q = [(0, start)]
    heapq.heapify(q)
    cost = [inf] * N
    cost[start] = 0
    while q:
        c, v = heapq.heappop(q)
        if c > cost[v]:
            continue
        for d, u in G[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(q, (tmp, u))
    return cost


G = [[] for _ in range(N)]
for _ in range(M):
    a, b, t = map(int, input().split())
    
    G[a].append((t, b))
    

res = dijkstra(r)
for i in res:
    if i == inf:
        print("INF")
        continue
    print(i)

Solution (Python):
from heapq import  heappop, heappush
def dijkstra(edges,start,first_index=0):
    d=[-1]*(len(edges)+first_index)
    hq=[(0,start)]
    while hq:
        c,v=heappop(hq)
        if d[v]!=-1:continue
        d[v]=c
        for to,cos in edges[v]:
            if d[to]==-1:heappush(hq,(c+cos,to))
    return d
v,e,st,*l=map(int,open(0).read().split())
ed=[[] for i in range(v)]
for a,s,d in zip(*[iter(l)]*3):
    ed[a].append((s,d))

for i in dijkstra(ed,st):
    print("INF"if -1==i else i )

Solution (Python):
n,m,s=map(int,input().split())

edge=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  edge[a].append((b,c))


from heapq import heappop,heappush
ans=[10 ** 20] * n
ans[s]=0
h=[[0,s]]
while h:
  c, v = heappop(h)
  if ans[v] < c:
    continue
  for u,t in edge[v]:
    if c + t < ans[u]:
      ans[u] = c + t
      heappush(h,[c + t,u])

for i in ans:
  if i == 10 ** 20:
    print("INF")
  else:print(i)

Solution (Python):
import heapq

if __name__ == "__main__":
    v, e, r = map(int, input().split())
    graph = [[] for _ in range(v)]
    for _ in range(e):
        s, t, d = map(int, input().split())
        graph[s].append((t, d))
    
    d = [float('inf')] * v
    d[r] = 0

    hq = [(0, r)]
    heapq.heapify(hq)

    while hq:
        cost, now = heapq.heappop(hq)
        if d[now] < cost:
            continue

        for nei in graph[now]:
            to = nei[0]
            c = nei[1]
            if d[to] > d[now] + c:
                d[to] = d[now] + c
                heapq.heappush(hq, (d[to], to))
    for i in range(v):
        if d[i] == float('inf'):
            print("INF")
        else:
            print(d[i])

Solution (Python):
from collections import defaultdict, deque

V, E, r = map(int, input().split(' '))

edges = defaultdict(set)

for _ in range(E):
    s, t, d = map(int, input().split(' '))
    edges[s].add((t, d))

costs = [-1] * V
costs[r] = 0

queue = deque()
queue.append(r)

while len(queue) > 0:
    s = queue.popleft()
    for t, d in edges[s]:
        if costs[t] < 0 or costs[s] + d < costs[t]:
            costs[t] = costs[s] + d
            queue.append(t)

for i in range(V):
    if costs[i] < 0:
        print('INF')
    else:
        print(costs[i])

Solution (Python):


import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
from queue import PriorityQueue
import itertools
from copy import deepcopy
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
class Edge():
    def __init__(self,x,y,cost=1):
        self.x=x
        self.y=y
        self.cost=cost
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def lcm(a,b):
    return a*b//math.gcd(a,b)
    G=[[] for a in range(n)]
    for edge in edges:
        x=edge[0]
        y=edge[1]
        G[x].append(y)
        if mukou:G[y].append(x)
    return G
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.cost))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.cost,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost

V,E,start=inputintlist()
edges=[]
for a in range(E):
    e=Edge(*inputintlist())
    edges.append(e)

mincost=dijkstra(edges,V,start)
for a in range(len(mincost)):
    print(ifelse(mincost[a]==inf,"INF",mincost[a]))

Solution (Python):

from heapq import heapify, heappop, heappush


def main():
    vertex, edge, root = map(int, input().split())
    max_val = 10 ** 10
    graph = [[] for _ in range(vertex)]
    for _ in range(edge):
        s, t, d = map(int, input().split())
        graph[s].append((t, d))
    dist = [max_val for _ in range(vertex)]
    dist[root] = 0
    q = []
    heapify(q)
    heappush(q, (0, root))
    while q:
        now_d, now_v = heappop(q)
        for next_v, length in graph[now_v]:
            now_dist = dist[now_v] + length
            if dist[next_v] > now_dist:
                dist[next_v] = now_dist
                heappush(q, (dist[next_v], next_v))

    for d in dist:
        print("INF" if d == max_val else d)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq

v, e, r = map(int, input().split())
g = [[] for _ in range(v)]
for i in range(e):
    s, t, d = map(int, input().split())
    g[s].append((d, t))

dist = [float("inf")] * v
visited = [False] * v
dist[r] = 0
visited[r] = True
candidate = []
for i in g[r]:
    heapq.heappush(candidate, i)
while len(candidate):
    
    minedge = heapq.heappop(candidate)
    if visited[minedge[1]]:
        continue
    c = minedge[1]
    dist[c] = minedge[0]
    visited[c] = True
    for i in g[c]:
        if not visited[i[1]]:
            heapq.heappush(candidate, (dist[c] + i[0], i[1]))

for i in dist:
    if i == float("inf"):
        print("INF")
    else:
        print(i)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m,r = map(int,readline().split())
g = [[] for i in range(n)]
for i in range(m):
    x,y,w = map(int,readline().split())
    g[x].append((w,y))
    


INF = 10**18
import heapq
push = heapq.heappush
pop = heapq.heappop
def dijkstra(s,g): 
    n = len(g)
    dist = [INF]*n
    dist[s] = 0
    used = [0]*n
    used[s] = 1
    hp = []
    for go in g[s]:
        push(hp,go)
    while hp:
        w,fr = pop(hp)

        if not used[fr]:
            dist[fr] = w
            used[fr] = 1
            for w,go in g[fr]:
                if not used[go]:
                    push(hp,(w+dist[fr],go))
    
    return dist

for i in dijkstra(r,g):
    print(i if i < INF else "INF")

Solution (Python):

from  heapq import heappush, heappop
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def main():
  V, E, r = LI()
  INF = 10**12

  if V == 1:
    print(0)
    exit()

  
  adj = [[] for _ in range(V)]

  for i in range(E):
    s, t, d = LI()
    adj[s].append((t,d))

  
  q = [(0,r)]
  C = [INF] * V
  C[r] = 0

  
  while len(q) > 0:
    
    cost, u = heappop(q)
  
    for v,d in adj[u]:
      tmp = C[u] + d
      if tmp < C[v]:
        C[v] = tmp
        heappush(q, (C[v], v))

  for c in C:
    if c == INF:
      print('INF')
    else:
      print(c)
    

if __name__ == "__main__":
  main()

Solution (Python):



from heapq import heappush, heappop


class PriorityQueue:
    def __init__(self):
        self._queue = []

    def push(self, value):
        heappush(self._queue, value)

    def pop(self):
        return heappop(self._queue)

    @property
    def empty(self):
        return not self._queue

    def __len__(self):
        return len(self._queue)

    def __contains__(self, item):
        return item in self._queue


V, E, R = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    f, t, d = map(int, input().split())
    edge[f].append((d, t))

queue = PriorityQueue()
queue.push((0, R))
visited = [float('inf')] * V
visited[R] = 0

while True:
    d, v = queue.pop()
    dist = visited[v]
    for e in edge[v]:
        if (e[0] + dist) < visited[e[1]]:
            visited[e[1]] = e[0] + dist
            queue.push((e[0] + dist, e[1]))

    if queue.empty:
        break
        
for i in visited:
    if i == float('inf'):
        print('INF')
    else:
        print(i)

Solution (Python):
from heapq import heapify, heappush, heappop

inf = float("inf")
def dijkstra(graph, start):  
    vsize = len(graph)
    dist = [inf] * vsize
    seen = [False] * vsize
    pq = []
    heapify(pq)

    dist[start] = 0
    heappush(pq, (0, start))  
    while pq:
        cost, u = heappop(pq)
        seen[u] = True
        if dist[u] < cost:
            continue
        for v, w in graph[u]:
            temp_cost = dist[u] + w
            if not seen[v] and temp_cost < dist[v]:
                dist[v] = temp_cost
                heappush(pq, (dist[v], v))
    return dist
V, E, r = map(int, input().split())
graph = [[] for _ in range(V)]
for _ in range(E):
    s, t, d = map(int, input().split())
    graph[s].append((t, d))
for min_cost in dijkstra(graph, r):
    print(min_cost if min_cost != inf else "INF")

Solution (Python):
import heapq

INF = 10 ** 9

v, e, r = map(int, input().split())
adjw = [[] for _ in range(v)]
for i in range(e):
    s, t, d = map(int, input().split())
    adjw[s].append((t, d))



def dijkstra(x):
    d = [INF] * x 
    d[r] = 0 
    hq = [(0, r)] 

    while hq:
        c, v = heapq.heappop(hq) 

        if d[v] < c: 
            continue

        for t, cost in adjw[v]: 
            if d[v] + cost < d[t]:
                d[t] = d[v] + cost
                heapq.heappush(hq, (d[t], t))
    
    return d

d = dijkstra(v)
for i in range(v):
    print(d[i]) if d[i] < INF else print('INF')

Solution (Python):
import heapq

V, E, r = map(int, input().split())

g = [[] for _ in range(V)]
for i in range(E):
    s, t, d = map(int, input().split())
    g[s].append((t, d))

dis = [float("inf") for _ in range(V)]
dis[r] = 0

pq = [(0, r)]
while pq:
    d, node = heapq.heappop(pq)
    if d > dis[node]: continue

    for nxt, cost in g[node]:
        if d + cost < dis[nxt]:
            dis[nxt] = d + cost
            heapq.heappush(pq, (dis[nxt], nxt))

for d in dis:
    if d == float("inf"):
        print("INF")
    else:
        print(d)

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d



n,w,r = map(int,input().split()) 

edge = [[] for i in range(n)]

for i in range(w):
    x,y,z = map(int,input().split())
    edge[x].append([z,y])
    
D=dijkstra_heap(r,edge)


for index in range(n):
    if D[index]==10**20:
        D[index]='INF'
    print(D[index])

Solution (Python):
import heapq
def dijkstra(s):
    
    d = [float('inf')]*n
    d[s] = 0
    
    used = [False]*n
    used[s] = True
    
    que = []
    for e in g[s]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in g[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d


n, w, r = [int(x) for x in input().split()] 
g = [[] for _ in range(n)]

for _ in range(w):
    x, y, z = [int(x) for x in input().split()]
    g[x].append([z, y])
    
for i in dijkstra(r):
    if i == float("inf"):
        print("INF")
    else:
        print(i)

Solution (Python):

import heapq
V, E ,r = list(map(int, input().split()))

INF = 10 ** 15



def dijkstra(edges, s):
    d = [INF for x in range(V)]
    d[s] = 0
    que = []
    heapq.heappush(que, (0,s))
    while len(que) > 0:
        u_d,u = heapq.heappop(que)
        if d[u] < u_d:
            continue
        for  v_d,v in edges[u]:
            if d[v] > d[u] + v_d:
                d[v] = d[u] + v_d
                heapq.heappush(que,(d[v],v))
    return d


cost = [[] for i in range(V)]

for i in range(E):
    x,y,z = map(int,input().split())
    cost[x].append((z, y))
    
d = dijkstra(cost, r)
for c in d:
    if c == INF:
        print("INF")
    else:
        print(c)

Solution (Python):
import sys, heapq
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
MOD = 1000000007
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def dijkstra(G, s):
    que = []
    d = [INF]*len(G)
    d[s] = 0
    heapq.heappush(que, (d[s], s))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for e in G[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(que, (d[e[0]], e[0]))
    return d

def resolve():
    V, E, r = LI()
    std = [LI() for _ in range(E)]

    edge = [[] for _ in range(V)]
    for i in std:
        edge[i[0]].append((i[1], i[2]))

    d = dijkstra(edge, r)

    for i in d:
        if i<INF:
            print(i)
        else:
            print('INF')

if __name__ == '__main__':
    resolve()

Solution (Python):
n,m,s=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  edge[a].append((b,c))
from heapq import heappop,heappush
ans=[10**20]*n
ans[s]=0
h=[[0,s]]
while h:
  c,v=heappop(h)
  if ans[v]<c:continue
  for u,t in edge[v]:
    if c+t<ans[u]:
      ans[u]=c+t
      heappush(h,[c+t,u])
for i in ans:
  if i==10**20:print("INF")
  else:print(i)

Solution (Python):

import heapq

N, M, r = list(map(int, input().split()))

D = {}
for i in range(N):
    D[i] = []

for _ in range(M):
    s, t, d = list(map(int, input().split()))
    D[s].append((t, d))

A = []
heapq.heappush(A, (0, r))

INF = float('inf')
results = [INF for _ in range(N)]
results[r] = 0

while A:
    cost, a = heapq.heappop(A)
    for t, d in D[a]:
        next_cost = cost + d
        if next_cost < results[t]:
            results[t] = next_cost
            heapq.heappush(A, (next_cost, t))

for result in results:
    if result == INF:
        print('INF')
    else:
        print(result)

Solution (Python):
from heapq import heappush,heappop,heapify
INF=10**30

def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        for c,v in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[v],v))
    return dist

V,E,r=map(int,input().split())
G=[[] for _ in range(V)]
for i in range(E):
    s,t,d=map(int,input().split())
    G[s].append((d,t))
dist=dijkstra(G,r,V)
for i in range(V):
    print(dist[i] if dist[i]!=INF else 'INF')

Solution (Python):
from collections import deque

V,E,r = map(int,input().split())
dlis = [[] for _ in range(V)]
mind = [10**10]*V

for _ in range(E):
  std = list(map(int,input().split()))
  dlis[std[0]].append([std[1],std[2]])
  
q = deque()
q.append([r,0])

while len(q) > 0:
  v = q.popleft()
  a = v[0]
  b = v[1]
  if mind[a] <= b:
    continue
  mind[a] = b
  for el in dlis[a]:
    aa = el[0]
    bb = b + el[1]
    if mind[aa] > bb:
      q.append([aa,bb])
    
for i in range(V):
  if mind[i] == 10**10:
    print("INF")
  else:
    print(mind[i])

Solution (Python):








import sys,collections
N,E,r = tuple(map(int,sys.stdin.readline().split())) 
sdd = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) 

G = [[] for i in range(N)]
for src,dist,d in sdd:
  G[src].append((dist,d))

INF = float("inf")
ALL = set(range(N))
mst = set()

distances = collections.defaultdict(lambda:INF)
distances[r] = 0

import heapq

dv = []
def add(u):
  mst.add(u)
  if len(mst) == N: return
  for v,w in G[u]:
    if not v in mst and w + distances[u] < distances[v]: 
      distances[v] = distances[u]+w
      heapq.heappush(dv, (distances[v],v))
  
  
  if not dv:
    return None
  d,v = heapq.heappop(dv)
  while dv and v in mst:
    d,v = heapq.heappop(dv)
  if v in mst:
    return None
  return v

n = add(r)
while n != None:
  n = add(n)
  

for i in range(N):
  if distances[i] == INF:
    print("INF")
  else:
    print(distances[i])