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 heapq
v, e, r = map(int, input().split( ))
E = [[] for _ in range(v)]
inf = 10**10
for _ in range(e):
    s,t,d = map(int, input().split( ))
    E[s].append((t,d))
D = [inf for _ in range(v)]

D[r] = 0
Q = []
heapq.heappush(Q, (0,r))


while Q:
    d,q = heapq.heappop(Q) 
    
    for n,c in E[q]:
        if D[n]>d+c:
            D[n] = d+c
            
            heapq.heappush(Q, (d+c,n))

for d in D:
    if d<inf:
        print(d)
    else:
        print("INF")

Solution (Python):
V,E,Start = map(int,input().split())
INF = 10**20
Edge = []
D = [INF]*V
for _ in range(E):
    Edge.append(list(map(int,input().split())))

D[Start] = 0
while True:
    update = False
    for i in range(E):
        fr   = Edge[i][0]
        to   = Edge[i][1]
        cost = Edge[i][2]

        if D[fr] != INF and D[to] > D[fr] + cost:
            D[to] = D[fr] + cost
            update = True
    if update == False:
        break
for d in D:
    if d == INF:
        print('INF')
    else:
        print(d)

Solution (Python):
N, M, S = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    s, t, d = map(int, input().split())
    G[s].append([t, d])


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0
    visited = [False] * n

    
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        visited[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (visited[to]) or (distances[to] <= new_dist):
                continue

            distances[to] = new_dist
            heapq.heappush(hq, (new_dist, to))

    return distances


ans = dijkstra(G, S)
for a in ans:
    print(a if a != float('inf') else 'INF')

Solution (Python):


import heapq
import os
import sys


def main():
    V, E, R = read_ints()
    G = [dict() for _ in range(V)]
    for _ in range(E):
        s, t, d = read_ints()
        G[s][t] = d
    print(*solve(V, E, R, G), sep='\n')


def solve(V, E, R, G):
    dists = [-1] * V
    q = []
    heapq.heappush(q, (0, R))
    while q:
        d, i = heapq.heappop(q)
        if dists[i] != -1:
            continue
        dists[i] = d
        for j, e in G[i].items():
            if dists[j] == -1:
                heapq.heappush(q, (d + e, j))
    return ['INF' if d == -1 else d for d in dists]





DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Solution (Python):

import heapq
def dijkstra(g, s):
    '''現時点で最短のものをheapqにぶち込みながら探索していく．
    '''
    n = len(g)
    dist = [10**9] * 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, c = map(int, input().split())
    g[s].append((t, c))
if e == 0:
    for i in range(v):
        if i == r:
            print(i)
        else:
            print("INF")
else:
    rets = dijkstra(g, r)
    for item in range(v):
        if rets[item] == 10**9:
            print("INF")
        else:
            print(rets[item])

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 _ in range(E):
    s, t, d = map(int, input().split())
    g[s].append((t, d))
ds = dijkstra(g, r)
for d in ds:
    print('INF' if d == INF else d)

Solution (Python):
from heapq import heappush, heappop
INF = 10**10
a,b,c = map(int,input().split())
d = [[] for i in range(a)]
for i in range(b):
    ta,tb,tc = map(int,input().split())
    d[ta].append((tb,tc))

def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    for i in range(a):
        print(dist[i] if dist[i] < INF else "INF")
dijkstra(a,d,c)

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

INF = sys.maxsize

v_num, e_num, src = map(int, input().split())
graph = [[] for _ in range(v_num)]

for _ in range(e_num):
  s, t, dist = map(int, input().split())
  graph[s].append((t, dist))

heap = []
dst = [INF for _ in range(v_num)]

heappush(heap, (0, src))
dst[src] = 0

while heap:
  dist, node = heappop(heap)
  for to, cost in graph[node]:
    if dst[to] > cost + dist:
      dst[to] = cost + dist
      heappush(heap, (cost + dist, to))

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

Solution (Python):
import heapq
INF = 100000000000000

def make_adj_list(v):
    adj_list = []
    for i in range(v):
        adj_list.append([])
    return adj_list

def dijkstra(v, e, adj_list, s):
    heap = []
    d = []
    pre = []
    for i in range(v):
        d.append(INF)
        pre.append(s)
    d[s] = 0
    heapq.heappush(heap, (0, s))
    while len(heap) != 0:
        candidate_d, now_v = heapq.heappop(heap)
        if d[now_v] < candidate_d:
            continue
        for v, cost in adj_list[now_v]:
            if d[v] > d[now_v] + cost:
                d[v] = d[now_v] + cost
                heapq.heappush(heap,(d[v], v))
                pre[v] = now_v
    return d, pre

def main():
    v, e, s = map(int, input().split())
    adj_list = make_adj_list(v)
    for i in range(e):
        a = [int(i) for i in input().split()]
        adj_list[a[0]].append((a[1], a[2]))
        
    d, pre = dijkstra(v, e, adj_list, s)

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

if __name__ == "__main__":
    main()

Solution (Python):
import heapq

def main():
    [V, E, r] = [int(num) for num in input().split()]

    edges = {}
    for i in range(V):
        edges[i] = []
    for i in range(E):
        num_list = [int(num) for num in input().split()]
        edges[num_list[0]].append((num_list[1], num_list[2]))

    dist = [10**10 for _ in range(V)]

    dist[r] = 0

    PQ = []

    heapq.heappush(PQ, (0, r))
    
    

    while len(PQ) > 0:
        (_, node_num) = heapq.heappop(PQ)

        for edge in edges[node_num]:
            
            new_len = dist[node_num] + edge[1]

            if new_len < dist[edge[0]]:
                heapq.heappush(PQ, (new_len, edge[0]))
                dist[edge[0]] = new_len

    for i in range(V):
        if dist[i] == 10**10:
            print('INF')
        else:
            print(dist[i])

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
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)) 
pq = []
dist = [10**10]*V
dist[r] = 0
heapq.heappush(pq, (0, r))
while pq:
        w, n = heapq.heappop(pq)
        for node, weight in Graph[n]:
                newlen = w + weight
                if newlen < dist[node]:
                        dist[node] = newlen
                        heapq.heappush(pq, (dist[node], node))
for i in dist:
        if i == 10**10:
                print("INF")
        else:
                print(i)

Solution (Python):
def main():
	V,E,r,*L = map(int,open(0).read().split())
	INF = float("inf")
	G = [[] for _ in range(V)]
	for s,t,c in zip(*[iter(L)]*3):
		G[s].append((t,c))
	for i in dijkstra(G,r):
		if i==INF:
			print("INF")
		else:
			print(i)

from heapq import heappop,heappush
def dijkstra(G:list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF]*V
	D[source] = 0
	vis = [False]*V
	H = [(0,source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D

if __name__=="__main__":main()

Solution (Python):

class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self,V=False):
        self.adj={}
        self.nodes={}
        
        if V>0:
            for v in range(0,V):
                self.nodes[v]={}
                self.adj[v]={}



    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          
        
        dist = {k:float('inf') for k in self.nodes}
        

        dist[start] = 0
        
        if N==0:
            return dist
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        
        

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    

        return dist

    def prim(self):

        import heapq

        nodes=list(self.nodes.keys())
        N=len(nodes)

        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(self.adj[X[0]][u],X[0],u))

        total_cost=0
        used={n:False for n in nodes}
        used[X[0]]=True
        while True:
            
            
            cost,u,v=heapq.heappop(unused)
            if used[v]:
                continue
            X.append(v)
            used[v]=True
            total_cost+=cost
            if len(X)==N:
                break

            for u in self.adj[v]:
                if used[u]:
                    continue
                heapq.heappush(unused,(self.adj[u][v],v,u))

        return total_cost




    def show(self):

        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()

        for u in self.adj:
            for v in self.adj[u]:

                
                G.add_edge(u,v,weight=self.adj[u][v])
                

        pos=nx.spring_layout(G)
        
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])

        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        
        
        plt.show()



def acinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    V,E,r=acinput()

    g=myGraph(V)


    for i in range(E):
        ss=acinput()
        
        g.add_directed_edge((ss[0],ss[1]),ss[2])

    
    
    
    dist=g.dijkstra(r)
    
    
    dist=sorted(dist.items())
    
    for node,val in dist:
        
        if val==float('inf'):
            val="INF"
        print(val)

Solution (Python):
from heapq import heappush, heappop
import sys
from typing import List, Tuple


if __name__ == "__main__":
    V, E, r = map(lambda x: int(x), input().split())

    edges: List[List[Tuple[int, int]]] = [[] for _ in range(V)]
    dists = [sys.maxsize for _ in range(V)]
    dists[r] = 0

    for _ in range(E):
        s, t, dist = map(lambda x: int(x), input().split())
        edges[s].append((t, dist))

    que: List[Tuple[int, int]] = []  
    heappush(que, (0, r))

    while que:
        dist, vertex = heappop(que)
        for to, cost in edges[vertex]:
            if cost + dist < dists[to]:
                dists[to] = cost + dist
                heappush(que, (cost + dist, to))

    for dist in dists:
        if sys.maxsize == dist:
            print("INF")
        else:
            print(dist)

Solution (Python):
class RadixHeap:
    __slots__ = ["data", "last", "siz", "used"]

    
    def __init__(self, N, C):
        self.data = [[] for i in range(C.bit_length() + 1)]
        self.last = self.siz = 0
        self.used = [0]*N

    def push(self, x, key):
        
        self.siz += 1
        self.data[(x ^ self.last).bit_length()].append((x, key))

    def pop(self):
        data = self.data
        used = self.used
        
        if not data[0]:
            i = 1
            while not data[i]:
                i += 1
            d = data[i]
            new_last, new_key = min(d)
            used[new_key] = 1
            for val in d:
                x, key = val
                if used[key]:
                    self.siz -= 1
                    continue
                data[(x ^ new_last).bit_length()].append(val)
            self.last = new_last
            data[i] = []
        else:
            new_last, new_key = data[0].pop()
            used[new_key] = 1
            self.siz -= 1
        return new_last, new_key

    def __len__(self):
        return self.siz

import sys
readline = sys.stdin.readline
write = sys.stdout.write

N, M, s = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, readline().split())
    G[a].append((b, c))

INF = 10**18
def dijkstra(N, G, s):
    que = RadixHeap(N, 10**9 + 1)

    dist = [INF]*N
    dist[s] = 0
    que.push(0, s)
    while que:
        cost, v = que.pop()
        if dist[v] < cost:
            continue
        for w, c in G[v]:
            if cost + c < dist[w]:
                dist[w] = r = cost + c
                que.push(r, w)
    return dist

dist = dijkstra(N, G, s)
for c in dist:
    write("INF\n" if c == INF else "%d\n" % c)

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop

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

D = [float("inf")]*v
D[r] = 0

q = []
heappush(q, (r, 0))
while q:
    now, dist = heappop(q)
    if D[now] < dist:
        continue

    for nxt, w in E[now]:
        t = dist + w
        if t < D[nxt]:
            D[nxt] = t
            heappush(q, (nxt, t))

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

Solution (Python):

import heapq as hp

V, E, s = map(int, input().split())
graph = [[] for _ in range(V)]
INF = 0
for _ in range(E):
    a, b, d = map(int, input().split())
    graph[a].append((d, b)) 
    
    INF = max(INF, d)

INF = INF*(E+1) + 1
D = [INF for _ in range(V)] 
D[s] = 0 
q = [] 
hp.heappush(q, (0, s))

while q:
    nd, np = hp.heappop(q) 
    if D[np] < nd: 
        continue
    for d, p in graph[np]:
        if D[p] > D[np] + d: 
            D[p] = D[np] + d
            hp.heappush(q, (D[p], p))

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

Solution (Python):

import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


from collections import defaultdict
import heapq
from collections.abc import MutableMapping


class HeapDict(MutableMapping):
    @staticmethod
    def _parent(i):
        return (i - 1) >> 1

    @staticmethod
    def _left(i):
        return (i << 1) + 1

    @staticmethod
    def _right(i):
        return (i + 1) << 1

    def __init__(self, *args, **kw):
        self.heap = []
        self.d = {}
        self.update(*args, **kw)

    def clear(self):
        del self.heap[:]
        self.d.clear()

    def __setitem__(self, key, value):
        if key in self.d:
            self.pop(key)
        wrapper = [value, key, len(self)]
        self.d[key] = wrapper
        self.heap.append(wrapper)
        self._decrease_key(len(self.heap) - 1)

    def _min_heapify(self, i):
        l = self._left(i)
        r = self._right(i)
        n = len(self.heap)
        if l < n and self.heap[l][0] < self.heap[i][0]:
            low = l
        else:
            low = i
        if r < n and self.heap[r][0] < self.heap[low][0]:
            low = r

        if low != i:
            self._swap(i, low)
            self._min_heapify(low)

    def _decrease_key(self, i):
        while i:
            parent = self._parent(i)
            if self.heap[parent][0] < self.heap[i][0]:
                break
            self._swap(i, parent)
            i = parent

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
        self.heap[i][2] = i
        self.heap[j][2] = j

    def __delitem__(self, key):
        wrapper = self.d[key]
        while wrapper[2]:
            parentpos = self._parent(wrapper[2])
            parent = self.heap[parentpos]
            self._swap(wrapper[2], parent[2])
        self.popitem()

    def __getitem__(self, key):
        return self.d[key][0]

    def __iter__(self):
        return iter(self.d)

    def popitem(self):
        """Remove and return a (key, value) pair with the lowest value"""
        wrapper = self.heap[0]
        if len(self.heap) == 1:
            self.heap.pop()
        else:
            self.heap[0] = self.heap.pop(-1)
            self.heap[0][2] = 0
            self._min_heapify(0)
        del self.d[wrapper[1]]
        return wrapper[1], wrapper[0]

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

    def peekitem(self):
        """Retuen a (key, value) pair with the lowest value"""
        return (self.heap[0][1], self.heap[0][0])


def main():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp"""
    V, E, r = readi(3)
    G = defaultdict(list)
    cost = dict()
    for _ in range(E):
        s, t, d = readi(3)
        G[s].append(t)
        cost[(s, t)] = d

    dist = arr(V, fill_value=INF)
    dist[r] = 0
    
    pq = [(dist[r], r)]
    while pq:
        
        _, u = heapq.heappop(pq)
        for v in G[u]:
            new_d = dist[u] + cost[(u, v)]
            if new_d < dist[v]:
                dist[v] = new_d
                
                heapq.heappush(pq, (dist[v], v))

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


if __name__ == "__main__":
    main()

Solution (Python):
v,e,r = map(int,input().split())
E = [tuple(map(int,input().split())) for one in range(e)]
D = [10**9 for two in range(v)]
D[r] = 0
for i in range(v):
    update = 0
    for s,t,d in E:
        if D[t]>D[s]+d:
            D[t] = D[s]+d
            update +=1
    if update == 0:
        break

for j in range(v):
    print(D[j] if D[j] != 10**9 else "INF")

Solution (Python):
v,e,r = map(int,input().split())
D = [float('inf')]*v
L = []
D[r] = 0
for i in range(e):
    s,t,d = map(int,input().split())
    L.append([s,t,d])
for i in range(v-1):
    update = False
    for j in range(e):
        a,b,c = L[j][0],L[j][1],L[j][2]
        if D[b] > D[a]+c:
            D[b] = D[a]+c
            update = True
    if not update:
        break
for i in range(v):
    if D[i] == float('inf'):
        print('INF')
    else:
        print(D[i])

Solution (Python):
def main():
    v,e,r=map(int,input().split())
    ans=[float('inf') for _ in range(v)]
    E = [tuple(map(int,input().split())) for _ in range(e)]
    ans[r]=0
    for i in range(v):
        update=False
        for s,t,c in E:
            if ans[t]>ans[s]+c:
                ans[t]=ans[s]+c
                update=True
        if not update:
            break
    for i in ans:
        if i==float('inf'):
            print("INF")
        else:
            print(i)
            
    
if __name__ == '__main__':
    main()

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):



from heapq import heappush, heappop
def dijkstra(g,start):
    dist = [1e18]*(len(g)) 
    dist[start] = 0
    q = [(0,start)] 
    pending = len(g)-1 
    while q and pending:
        c,v = heappop(q)
        if dist[v] < c: continue
        pending -= 1
        for to, cost in g[v]:
            if dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(q, (dist[to], to))
    return dist

v,e,r = [int(i) for i in input().split()]

g = [[] for _ in range(v)]
for _ in range(e):
    a,b,c = [int(i) for i in input().split()]
    g[a].append((b, c))

for i in dijkstra(g,r):
    if i == 1e18: print("INF")
    else: print(i)

Solution (Python):

"""
Created on Sat May 18 23:11:54 2019

@author: maezawa
"""

import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        0-indexedでなくてもよいことに注意
        s = 始点
        return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d
    
v, e, r = list(map(int, input().split()))
graph1 = Dijkstra()
for _ in range(e):
    si, ti, di = list(map(int, input().split()))
    graph1.add(si, ti, di, directed=True)
    
res = graph1.Dijkstra_search(r)
for i in range(v):
    ans = res[i]
    if ans == float('inf'):
        print('INF')
    else:
        print(ans)

Solution (Python):

import math

graph = []

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

lens = [float('inf') for i in range(V)]
lens[r] = 0

for i in range(E) :
    start, desti, distance = map(int, input().split())
    graph.append([start, desti, distance])
    

while True :
    
    flag = True
    for q in graph :
        
        if lens[q[1]] > lens[q[0]] + q[2]:
          lens[q[1]] = min(lens[q[1]], lens[q[0]] + q[2])
          flag = False         
    if flag:
      break

for item in lens :
    if math.isinf(item):
        print("INF")
    else :
        print(item)

Solution (Python):
import sys
from heapq import heappush
from heapq import heappop
from collections import deque


n_V, n_E, r = map(int, input().split())

E = [[] for _ in range(n_V)]
for i in range(n_E):
    v, e, c = map(int, input().split())
    E[v].append((e, c))


D = [sys.maxsize for _ in range(n_V)]
D[r] = 0

h = []
heappush(h, (D[r], r))


while len(h) != 0:
    _, index = heappop(h)

    for e, c in E[index]:
        d = D[index] + c
        if D[e] > d:
            D[e] = d
            heappush(h, (d, e))


for d in D:
    if d == sys.maxsize:
        print('INF')
    else:
        print(d)

Solution (Python):
if __name__=='__main__':
    V_MAX = 100000
    E_MAX = 500000
    INF = float('inf')

    v,e,r=(int(x) for x in  input().split())
        
    e_from = []
    e_to = []
    e_cost= []
    dist=[]

    for i in range(e):
        f, t, c=(int(x) for x in  input().split())
        e_from.append(f)
        e_to.append(t)
        e_cost.append(c)

    for i in range(v):
        dist.append(INF)
   
    dist[r] = 0
   
    while True:
        flag = 1
        for i in range(e):
            if (dist[e_from[i]] != INF) and (dist[e_to[i]] > dist[e_from[i]]+e_cost[i]):
                dist[e_to[i]] = dist[e_from[i]] + e_cost[i]
                flag=0

        if flag:
            break
    

    for i in range(v):
        if dist[i] ==  INF:
            print("INF")
        else:
            print(dist[i])

Solution (Python):
import sys
import heapq
MAX_INT = float("Inf")

def find_shortest_path_with_weight(graph,start_v,v_num):
    distance = [MAX_INT]*v_num
    distance[start_v] = 0
    queue = []*v_num
    queue.append((distance[start_v],start_v))
    while True:
        if(len(queue)==0):
            break
        
        
        weight,v = queue.pop(0)
        if(distance[v] < weight):
            continue
        for i,(to,weight) in enumerate(graph[v]):
            if(weight + distance[v] < distance[to]):
                distance[to] = weight + distance[v]
                
                heapq.heappush(queue,(distance[to],to))
    
    for i in distance:
        if(i < MAX_INT):
            print(i)
        else:
            print("INF")

        
if __name__ == '__main__':
    v_num,e_num,start_v = map(int, input().split())
    
    graph = [ [] for _ in range(v_num)]
    for i in range(e_num):
        s,t,w = map(int, input().split())
        graph[s].append((t,w))
    find_shortest_path_with_weight(graph,start_v,v_num)

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


class Dijkstra:
    class Edge:
        def __init__(self, end, cost):
            self.to = end
            self.cost = cost

    def __init__(self, node_size, inf):
        self._node = node_size
        self._graph = [[] for _ in range(self._node)]
        self.inf = inf
        self.dist = [self.inf for _ in range(self._node)]

    def add_edge(self, st, ed, cs):
        self._graph[st].append(self.Edge(ed, cs))

    def solve(self, start):
        que = []
        self.dist[start] = 0
        heappush(que, (0, start))
        while que:
            cur_cost, cur_vertex = heappop(que)
            if self.dist[cur_vertex] < cur_cost:
                continue
            for e in self._graph[cur_vertex]:
                if self.dist[e.to] > cur_cost + e.cost:
                    self.dist[e.to] = cur_cost + e.cost
                    heappush(que, (self.dist[e.to], e.to))


if __name__ == '__main__':
    V, E, r = map(int, sys.stdin.readline().split())
    dk = Dijkstra(V, 10 ** 10)
    for i in range(E):
        s, t, d = map(int, sys.stdin.readline().split())
        dk.add_edge(s, t, d)
    dk.solve(r)
    for value in dk.dist:
        if value == dk.inf:
            sys.stdout.write("INF\n")
        else:
            sys.stdout.write("%s\n" % value)