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


def dijkstra(g, s):
    queue = [[0, s]]
    v = len(g)
    d = [float("inf")] * v
    d[s] = 0
    while queue:
        i, j = heapq.heappop(queue)
        if d[j] > i:
            continue
        for e in g[j]:
            if d[e[0]] > d[j] + e[1]:
                d[e[0]] = d[j] + e[1]
                heapq.heappush(queue, [d[e[0]], e[0]])

    return d


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((t, d))

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

Solution (Python):
import heapq
def dijkstra(start:int):
    """priority_queue ver. O(|E|log|V|)
    """
    global dist 
    global edges 
    dist[start] = 0
    q = [(0,start)] 
    while q:
        d_cur,cur = heapq.heappop(q)
        if dist[cur] < d_cur: 
            continue
        for nex,cost in edges[cur]:
            if dist[nex] > dist[cur]+cost:
                dist[nex] = dist[cur]+cost
                heapq.heappush(q, (dist[nex], nex))


if __name__ == "__main__":
    V,E,start = map(int, input().split())
    edges = [[] for _ in range(V)]
    for _ in range(E):
        s,t,d = map(int, input().split())
        edges[s].append((t, d))
    dist = [float('inf') for _ in range(V)]
    dijkstra(start)
    for di in dist:
        if di==float('inf'):
            print("INF")
        else:
            print(di)

Solution (Python):
from heapq import heappop, heappush


class E:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost



N, M, r = [int(x) for x in input().split()]

G = [[] for x in range(N)]
D = [float('inf')] * N
V = [False] * N

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


pq = [(0, r)]
D[r] = 0

while pq:
    u = heappop(pq)
    if V[u[1]]:
        continue
    for v in G[u[1]]:
        if v.cost + u[0] < D[v.to]:
            D[v.to] = v.cost + u[0]
            heappush(pq, (D[v.to], v.to))
    V[u[1]] = True

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

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**7) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


'''
ダイクストラ法
----------
input
    graph: 隣接リスト (list)
    start: 開始ノード番号
    INF  : distの最大値

output
    dist : startから各ノードへの距離 (list)
    
'''
from heapq import heappush, heappop

def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF]*n
    visited = [False]*n
    
    dist[start] = 0
    que = [(0, start)]
    
    while que:
        cost, cur = heappop(que)
        
        if visited[cur]:
            continue
        
        visited[cur] = True
        
        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))
      
    return dist

n,e,r = li()
graph = [[] for _ in range(n)]

for _ in range(e):
    s,t,d = li()
    graph[s].append((t, d))

INF = 1<<62
dist = dijkstra(graph, r, INF)

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

Solution (Python):
import sys
from heapq import heappush, heappop
readline = sys.stdin.readline
from collections import defaultdict
vertices, edges, start = map(int, readline().split())
connect = defaultdict(list)
cost = defaultdict(dict)
answer = ["INF" for n in range(vertices)]
for _ in range(edges):
    s, t, w = map(int, readline().split())
    connect[s].append(t)
    cost[s].update({t:w})
 
 
now = start
weight = 0
p_queue = []
heappush(p_queue, (0, now))
visited = set()
while p_queue:
    weight, now = heappop(p_queue)
    if now in visited:
        continue
    visited |= {now}
    answer[now] = weight
    for c in connect[now]:
        if c not in visited:
            heappush(p_queue, (weight + cost[now][c], c))
for a in answer:
    print(a)

Solution (Python):
import heapq


graph = {}
inf = 1

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

for i in range(m):
    src, nxt, dst = map(int, input().split())
    if src not in graph:
        graph[src] = {}
    graph[src][nxt] = dst
    inf += dst

cost = [inf] * n
cost[s] = 0

heap = []
heapq.heappush(heap, (0, s))

while len(heap) > 0:
    pair = heapq.heappop(heap)
    c, v = pair[0], pair[1]

    if cost[v] < c:
        continue
    if v not in graph:
        continue

    for nxt, dst in graph[v].items():
        if cost[nxt] > cost[v] + dst:
            cost[nxt] = cost[v] + dst
            heapq.heappush(heap, (cost[nxt], nxt))

for c in cost:
    print(c) if c < inf else print('INF')

Solution (Python):
from heapq import heappush, heappop

INF = float('inf')

"""
class UnWeightedEdge:
    def __init__(self, src, to):
        self.src = src
        self.to = to
"""

class WeightedEdge():
    def __init__(self, src, to, cost):
        self.src = src
        self.to = to
        self.cost = cost

def Dijkstra(G, s):
    dist = [INF] * len(G)
    dist[s] = 0
    pq = []
    heappush(pq, (0, s))
    while len(pq) != 0:
        top = heappop(pq)
        cost = top[0]
        v = top[1]
        if dist[v] < cost:
            continue
        for edge in G[v]:
            next_cost = cost + edge.cost
            if dist[edge.to] <= next_cost:
                continue
            dist[edge.to] = next_cost
            heappush(pq, (next_cost, edge.to))
    return dist

if __name__ == "__main__":
    """
    入力
    V E r (V:=頂点の数, E:=辺の数, r:=始点のインデックス)
    src0 to0 cost0
    src1 to1 cost1
    .
    .
    srcE-1 toE-1 costE-1
    """
    V, E, r = map(int, input().split())
    G = [[] for i in range(V)]
    for i in range(E):
        src, to, cost = map(int, input().split())
        G[src].append(WeightedEdge(src, to, cost))
    dist = Dijkstra(G, r)
    for i in range(V):
        if dist[i] == INF:
            print("INF")
        else:
            print(dist[i])

Solution (Python):
import sys
import os
import collections
 
def input(f):
    global v, e, r, s, t, d, g
     
    v, e, r = map(int, f.readline().split())
    s = []
    t = []
    d = []
    for _ in range(e):
        s_, t_, d_ = map(int, f.readline().split())
        s.append(s_)
        t.append(t_)
        d.append(d_)
         
    g = [list() for _ in range(v)]
    for i in range(e):
        g[s[i]].append(i)
 
def solve():
    inf = sys.maxint
    q = collections.deque()
    q.append(r)
    mincost = [inf]*v
    mincost[r] = 0
    while len(q) > 0:
        cur = q.popleft()
        for e in g[cur]:
            if mincost[t[e]] == inf or mincost[t[e]] > mincost[cur] + d[e]:
                mincost[t[e]] = mincost[cur] + d[e]
                q.append(t[e])
     
    for i in range(v):
        if mincost[i] == inf:
            print('INF')
        else:
            print(mincost[i])
 
with open(os.environ.get('INPUT') or '/dev/stdin') as f:
    input(f)
    solve()

Solution (Python):
from heapq import heappush, heappop

INF = 10 ** 12

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

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

que = []
heappush(que, (0, r))
dist_lst[r] = 0

while que:
    dist, node = heappop(que)
    for to, cost in edges_lst[node]:
        if dist_lst[to] > cost + dist:
            dist_lst[to] = cost + dist
            heappush(que, (cost + dist, to))

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

Solution (Python):
from heapq import heappush,heappop
V,E,r = map(int,input().split())
edges = [[] for _ in range(V)]
for _ in range(E):
    s,t,d = map(int,input().split())
    edges[s].append((t,d))
que = []
mindists = [float("inf")]*V
mindists[r] = 0
heappush(que,(0,r))
while que:
    ccost,cnode = heappop(que)
    if mindists[cnode] < ccost: continue
    for nnode,ncost in edges[cnode]:
        tcost = ccost+ncost
        if mindists[nnode] > tcost:
            mindists[nnode] = tcost
            heappush(que,(tcost,nnode))
print("\n".join(str(e) if e != float("inf") else "INF" for e in mindists))

Solution (Python):
import heapq

V, E, start = map(int, input().split())
G = [[] for _ in range(V)]
for i in range(E):
    si, ti, di = map(int, input().split())
    G[si].append((ti, di))

d = [float('INF')] * V
used = [False] * V
prev = [-1] * V

def Dijkstra(s):
    d[s] = 0
    q =[]
    heapq.heappush(q, (0, s))
    while len(q) > 0:
        dist, v  = heapq.heappop(q)
        if d[v] < dist:
            continue
        for j, cost in G[v]:
            if d[j] > d[v] + cost:
                d[j] = d[v] + cost
                heapq.heappush(q, (d[j], j))
                prev[j] = v

Dijkstra(start)
for i in range(V):
    if d[i] == float('inf'):
        print('INF')
    else:
        print(d[i])

Solution (Python):

from collections import namedtuple
from heapq import heappop, heappush


WEIGHT_MAX = 10 ** 10
WeightedEdge = namedtuple('WeightedEdge', ('src', 'dest', 'weight'))


class Digraph:
    def __init__(self, v):
        self.v = v
        self.edges = [[] for _ in range(v)]

    def add(self, edge):
        self.edges[edge.src].append(edge)

    def adj(self, v):
        return self.edges[v]


def sp_dijkstra(graph, s):
    def push_node(v):
        if v in index:
            index[v][2] = False
        node = [dists[v], v, True]
        heappush(nodes, node)
        index[v] = node

    def pop_node():
        while nodes:
            node = heappop(nodes)
            if node[2]:
                return node[1]
        return None

    def relax(edge):
        s, t, w = edge
        if dists[t] > dists[s] + w:
            dists[t] = dists[s] + w
            srcs[t] = s
            push_node(t)

    nodes = []
    index = {}
    dists = [WEIGHT_MAX] * graph.v
    dists[s] = 0
    srcs = [-1] * graph.v

    v = s
    while v is not None:
        for e in graph.adj(v):
            relax(e)
        v = pop_node()

    return [None if dists[v] == WEIGHT_MAX else dists[v]
            for v in range(graph.v)]


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

    digraph = Digraph(v)
    for _ in range(e):
        edge = WeightedEdge(*[int(i) for i in input().split()])
        digraph.add(edge)

    for w in sp_dijkstra(digraph, r):
        if w is None:
            print('INF')
        else:
            print(w)


if __name__ == '__main__':
    run()

Solution (Python):
V, E, r = map(int, input().split())
paths = []

for i in range(E) :
    s, t, d = map(int, input().split())
    
    paths.append([s, t, d])
    
INF = 10**20
n = [INF for x in range(V)]
n[r] = 0

while True :
    break_flg = True
    
    for p in paths :
        if n[p[0]] + p[2] < n[p[1]] :
            n[p[1]] = min(n[p[1]], n[p[0]] + p[2])
            break_flg = False
            
    if break_flg == True :
        break

for i in n :
    if i == INF :
        print("INF")
    else :
        print(i)

Solution (Python):
import sys
import heapq as h

inf = sys.maxsize


class heapq:
    def __init__(self):
        self.q = []

    def push(self,v):
        h.heappush(self.q, v)
    
    def pop(self):
        return h.heappop(self.q)

    def is_empty(self):
        return len(self.q) == 0


V,e,r=(int (i)for i in input().split())

G=[[] for i in range(V)]
for j in range(e):
    f,t,cost=(int (i)for i in input().split())
    G[f].append((t,cost))
dist=[inf]*100000
visited=[False]*100000
a=heapq()
a.push((0,r))
def end(visited):
    for i in visited:
        if i==False:
            return False
    return True
while(not a.is_empty()):
    (cur_dist,u)=a.pop()
    if not visited[u]:
        
        dist[u]=cur_dist
        
        visited[u]=[True]
        for (v,cost) in G[u]:
            if not visited[v] and dist[u]+cost<dist[v]:
                a.push((dist[u]+cost,v))

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