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
from typing import List, TypeVar, Generic
T = TypeVar('T', int, float)


class Edge(Generic[T]):
    def __init__(self, dst: int, weight: T) -> None:
        self.dst: int = dst
        self.weight: T = weight

    def __lt__(self, e: 'Edge') -> bool:
        return self.weight > e.weight


class Graph(Generic[T]):
    def __init__(self, V: int) -> None:
        self.V: int = V
        self.E: List[List[Edge[T]]] = [[] for _ in range(V)]

    def add_edge(self, src: int, dst: int, weight: T) -> None:
        self.E[src].append(Edge(dst, weight))


class Node(Generic[T]):
    def __init__(self, v: int, cost: T) -> None:
        self.v: int = v
        self.cost: T = cost

    def __lt__(self, n: 'Node') -> bool:
        return self.cost < n.cost


class ShortestPath(Generic[T]):
    def __init__(self, G: Graph[T], inf: T = 10**9) -> None:
        self.G: Graph[T] = G
        self.inf: T = inf
        self.dist: List[T] = [self.inf] * self.G.V  
        self.prev: List[int] = [-1] * self.G.V  

    def run(self, start: int, goal: int = -1) -> None:
        que: List[Node] = list()
        self.dist[start] = 0
        heapq.heappush(que, Node[T](start, 0))

        while que:
            node: Node[T] = heapq.heappop(que)
            if self.dist[node.v] < node.cost:
                continue
            if goal != -1 and node.v == goal:
                return
            for edge in self.G.E[node.v]:
                if self.dist[node.v] + edge.weight < self.dist[edge.dst]:
                    self.dist[edge.dst] = self.dist[node.v] + edge.weight
                    heapq.heappush(que, Node(edge.dst, self.dist[edge.dst]))
                    self.prev[edge.dst] = node.v

    def getPath(self, end: int) -> List[int]:
        path: List[int] = [end]
        while self.prev[end] != -1:
            end = self.prev[end]
        return path[::-1]

def main() -> None:
    V, E, start = map(int, input().split())
    graph = Graph[int](V)
    for _ in range(E):
        s, t, d = map(int, input().split())
        graph.add_edge(s, t, d)
    inf = int(1e10)
    sp = ShortestPath[int](graph, inf)
    sp.run(start)
    for i in range(V):
        print(sp.dist[i] if sp.dist[i] != inf else "INF")

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop

INF = 10 ** 20

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

for _ in range(e_num):
  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):
import sys
from collections import deque

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

edge_info=[0]*v;
for i in range(v):
    edge_info[i] = []

for i in range(e):
    e1, e2, w = map(int, input().split());
    edge_info[e1].append((e2,w))

v_q=deque();

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
v_q.append((0,r))
while(len(v_q) != 0):
    cost,u = v_q.popleft()
    if(cost > d[u]):
        continue
    for j in range(len(edge_info[u])):
        e2,w = edge_info[u][j]
        alt = cost+w
        if(d[e2] > alt):
            d[e2] = alt
            v_q.append((alt,e2))

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

Solution (Python):
import sys
from collections import deque

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

edge_info=[0]*v;
for i in range(v):
    edge_info[i] = []

for i in range(e):
    e1, e2, w = map(int, input().split());
    edge_info[e1].append((e2,w))

v_q=deque();

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
v_q.append((0,r))
while(len(v_q) != 0):
    cost,u = v_q.popleft()
    if(cost > d[u]):
        continue
    for j in range(len(edge_info[u])):
        e2,w = edge_info[u][j]
        alt = cost+w
        if(d[e2] > alt):
            d[e2] = alt
            v_q.append((alt,e2))

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

Solution (Python):
import heapq
from enum import Enum, auto

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

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

    def __lt__(self, node):
        return self.w < node.w

color = []      
d = []          


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

def dijkstra(s):
    global d, color
    color = [Color.WHITE for i in range(V)]
    d = [float('inf') for i in range(V)]
    d[s] = 0

    pqueue = [Node(s, 0)]
    while len(pqueue) >= 1:
        u = heapq.heappop(pqueue).n
        color[u] = Color.BLACK

        for v, w in adj_list[u]:
            if color[v] != Color.BLACK:
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    color[v] = Color.GRAY
                    heapq.heappush(pqueue, Node(v, d[v]))

dijkstra(r)
for w in d:
    if w == float('inf'):
        print('INF')
    else:
        print(w)

Solution (Python):


V,E,r = map(int, input().split())
edges = []
for _ in range(E):
    tmp = [int(x) for x in input().split()]
    edges.append(tmp)

d = [float('inf') for _ in range(V)]
d[r] = 0

for _ in range(V-1):
    count = 0
    for x in edges:
        s,t,w = x
        if d[t] > d[s] + w:
            count += 1
            d[t] = d[s] + w
    if count == 0:
        break

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

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

if __name__ == '__main__':
    V, E, r = map(int, input().split())
    edge = [[] for _ in range(V)]
    d = [math.inf] * V
    que = []
    for _ in range(E):
        s, t, c = map(int, input().split())
        edge[s].append([t, c])

    d[r] = 0
    heap = [(d[r], r)]
    while heap:
        du, u = heappop(heap)
        for t, c in edge[u]:
            if d[t] > du + c:
                d[t] = du + c
                heappush(heap, (d[t], t))

    for di in d:
        print('INF' if math.isinf(di) else di)

Solution (Python):
from heapq import heappush, heappop
INF = float('inf')
def dijkstra(s, n, adj):
    dist = [INF] * n
    hq = [(0, s)]
    dist[s] = 0
    seen = [False] * n
    while hq:
        v = heappop(hq)[1]
        seen[v] = True
        for to, cost in adj[v]:
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

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

ans = dijkstra(r, v, adj)
for i in ans:
    if i == float('inf'):
        print('INF')
    else:
        print(i)

Solution (Python):
import sys
import heapq

V, E, r = map(int, sys.stdin.readline().strip().split())

G = [[] for _ in range(V)]
for e in range(E):
    s, t, d = map(int, sys.stdin.readline().strip().split())

    G[s].append((t, d))
    


distance = ['INF'] * V  
distance[r] = 0
que = []

for u, d_u in G[r]:
    heapq.heappush(que, (d_u, u))

while que:
    d_tot, u = heapq.heappop(que)
    if distance[u] is not 'INF':
        continue

    distance[u] = d_tot
    for v, d_v in G[u]:
        if distance[v] is not 'INF':  
            continue
        heapq.heappush(que, (d_tot + d_v, v))

for i in distance:
    print(i)

Solution (Python):
def dijkstra(vertex_num, edge_list, start):
    import heapq
    
    d = [float("inf")] * vertex_num
    
    d[start] = 0
    hq = []
    heapq.heappush(hq, [0, start])
    while len(hq) > 0:
        cost, frm = heapq.heappop(hq)
        for cost, to in edge_list[frm]:
            if d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                heapq.heappush(hq, [d[to], to])
    return d

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

adj_list = [[] for _ in range(n)]

for i in range(m):
    frm, to, cost = map(int, input().split())
    adj_list[frm].append([cost, to])

d = dijkstra(n, adj_list, s)

for i in range(len(d)):
    print(d[i]) if d[i] != float("inf") else print("INF")

Solution (Python):



import heapq

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


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

for i in range(e):
    _s, _t, _d = map(int, input().split())

    g_l[_s].append([_t,_d])

def djkstra(s):
    ans_l = [float("INF")] * v
    _l = [[0,s]]
    heapq.heapify(_l)
    while len(_l) > 0:
        _c, _v = heapq.heappop(_l)
        if ans_l[_v] < _c:
            continue
        ans_l[_v] = _c
        for _t, _d in g_l[_v]:
            if ans_l[_t] > _c + _d:
                heapq.heappush(_l,[_c + _d, _t])
    return ans_l

ans_l = djkstra(r)
for i in range(v):
    print(str(ans_l[i]).upper())

Solution (Python):


from pprint import pprint
import heapq
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


N, M, source = map(int, input().split())
adj_list = [[] for v in range(N)]
for _ in range(M):
    u, v, w = map(int, input().split())
    adj_list[u].append([v, w])



def dijkstra(n_nodes, adj_list, source):
    dist = [0 if v == source else INF for v in range(n_nodes)]
    priority_queue = [[dist[source], source]]

    while priority_queue:
        current_distance, current = heapq.heappop(priority_queue)
        if current_distance > dist[current]:
            continue
        for neighbor, distance in adj_list[current]:
            if current_distance + distance < dist[neighbor]:
                dist[neighbor] = current_distance + distance
                heapq.heappush(priority_queue, [dist[neighbor], neighbor])

    return dist


dist = dijkstra(N, adj_list, source)

for v in range(N):
    if dist[v] == INF:
        print('INF')
    else:
        print(dist[v])

Solution (Python):
V,E,start = map(int,input().split())
node_edges = [[] for _ in range(V)]
for i in range(E):
    s,g,cost = map(int,input().split())
    node_edges[s].append([cost,g])
import heapq
n = V
def dijkstra_heap(s,node_edges):
    '''
    node_edgesはindがノード番号、valueが[コスト,行先node],[コスト,行先node]..]というindノードからのエッジのリスト
    ノードの入力は0-indexedに修正してから用いる
    returnはノードごとの最小コストを格納したリスト
    '''
    
    d = [float("inf")] * n
    used = [False] * n 
    d[s] = 0
    used[s] = True
    edgelist = []
    
    for e in node_edges[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        
        
        minedge = heapq.heappop(edgelist)
        
        if used[minedge[1]]:
            continue
        v = minedge[1]
        
        d[v] = minedge[0]
        used[v] = True
        for e in node_edges[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
ls = dijkstra_heap(start,node_edges)
for i in range(n):
    value = ls[i]
    if value == float('inf'):
        value = "INF"
    print(value)

Solution (Python):
import heapq

INF = 10 ** 9
V, E, r = map(int, input().split())
edge_list = [[] for _ in range(V)]
dist_list = [INF] * V
for _ in range(E):
  s, t, d = map(int, input().split())
  edge_list[s].append((t, d))

q = []
heapq.heapify(q)
heapq.heappush(q, (0, r))
dist_list[r] = 0

while len(q) != 0:
  dist, node = heapq.heappop(q)
  for to, cost in edge_list[node]:
    if dist + cost < dist_list[to]:
      dist_list[to] = dist + cost
      heapq.heappush(q, (dist + cost, to))

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

Solution (Python):
import heapq
import math
INF=math.inf
V, E, r = map(int, input().split())
edges = [[] for i in range(V)]
dist = [INF] * V
visited = [0] * V
node_heap=[]
for i in range(E):
    lst = list(map(int, input().strip().split()))
    edges[lst[0]].append([lst[0],lst[1],lst[2]])

dist[r] = 0
cur_node=r     
visited[r] = 1

for cur_edges in edges[cur_node]:
    heapq.heappush(node_heap,[dist[r]+cur_edges[2],cur_edges[1]]) 
while node_heap:
    shortest_route = heapq.heappop(node_heap)
    if visited[shortest_route[1]]:
        continue
    cur_node = shortest_route[1]
    dist[cur_node]=shortest_route[0]
    for cur_edges in edges[cur_node]:
        if visited[cur_edges[1]]==0:
            heapq.heappush(node_heap, [dist[cur_node] + cur_edges[2], cur_edges[1]])
    visited[cur_node]=1

for i in range(V):
    if dist[i] == INF:
        print("{}".format("INF"))
    else:
        print("{}".format(dist[i]))

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


def dijkstra(s, n): 
    dist = [INF] * n
    hq = [(0, s)] 
    dist[s] = 0
    seen = [False] * n 
    while hq:
        v = heappop(hq)[1] 
        seen[v] = True
        for to, cost in adj[v]: 
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist


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


d = dijkstra(r, v)
for i in d:
    if i != 1000000000: print(i)
    else: print("INF")

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

n, e, k= map(int, input().split())




edge_list = [[] for i in range(n)]
for _ in range(e):
    s, t, u = map(int, input().split())
    edge_list[s].append([u, t])

    
    



def dijkstra(edges, start):
    
    d = [float("inf")] * n
    used = [False] * n
    d[start] = 0
    used[start] = True
    
    node_cost_list = []

    for e in edges[start]:
        heappush(node_cost_list, e)
    while len(node_cost_list):
        min_cost_node = heappop(node_cost_list)
        if used[min_cost_node[1]]:
            continue
        v = min_cost_node[1]
        d[v] = min_cost_node[0]
        used[v] = True
        for z in edges[v]:
            if not used[z[1]]:
                heappush(node_cost_list, [z[0]+d[v], z[1]])
    return d


if __name__ == "__main__":
    for i in dijkstra(edge_list,k):
        if i == float("inf"):
            print("INF")
        else:
            print(i)


'''
4 6 1
0 1 1
0 2 4
2 0 1
1 2 2
3 1 1
3 2 5
'''

Solution (Python):
import sys
from collections import defaultdict
from queue import Queue


def main():
    input = sys.stdin.buffer.readline
    n, m, r = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(m):
        s, t, d = map(int, input().split())
        graph[s].append((t, d))
    que = Queue()
    que.put(r)
    dist = [-1] * n
    dist[r] = 0
    while not que.empty():
        e = que.get()
        dist_now = dist[e]
        for nxt, cost in graph[e]:
            dist_nxt = dist[nxt]
            if dist_nxt == -1 or dist_nxt > dist_now + cost:
                dist[nxt] = dist_now + cost
                que.put(nxt)
    for d in dist:
        print(d if d != -1 else "INF")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from heapq import heappush, heappop
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    V, E, r = map(int, readline().split())
    G = [[] for _ in range(V)]

    for _ in range(E):
        u, v, d = map(int, readline().split())
        G[u].append([v,d])

    dist = [INF] * V
    que = [(0, r)]
    dist[r] = 0
    while que:
        c, v = heappop(que)
        
        
        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 dist:
        print('INF' if i==INF else i)
if __name__ == '__main__':
    main()

Solution (Python):
import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

inf = 10 ** 18
dist = [inf] * N
dist[r] = 0
que = [(0, r)]
while que:
    c, s = heapq.heappop(que)
    if dist[s] < c:
        continue
    d = dist[s]
    for t, cost in edge[s]:
        if dist[t] > d + cost:
            dist[t] = d + cost
            heapq.heappush(que, (d + cost, t))

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

Solution (Python):
from collections import defaultdict
import heapq

V, E, r = map(int, input().split())
edges = defaultdict(list)
for _ in range(E):
    s, t, d = map(int, input().split())
    edges[s].append((t, d))

dists = {}  
q = [(0, r)]

while q:
    dist, node = heapq.heappop(q)
    if node in dists:
        continue
    dists[node] = dist
    for t, d in edges[node]:
        if t not in dists:
            heapq.heappush(q, (dist + d, t))

for i in range(V):
    if i in dists:
        print(dists[i])
    else:
        print('INF')

Solution (Python):
from sys import stdin
import math
import heapq



V, E, r = map(lambda x: int(x), stdin.readline().split(' '))


adjacency_list = [[] for x in range(V)] 
for i in range(E):
    s, t, d = map(lambda x: int(x), stdin.readline().split(' '))
    adjacency_list[s].append([t, d])

distance = [(math.inf, id) for id in range(V)]
output_distance = [math.inf for id in range(V)]
checked_set = set()
distance[r] = (0, r)

distance.sort()
while len(checked_set) < V:
    target = heapq.heappop(distance)
    target_id = target[1]
    if target_id in checked_set:
        continue
    target_dis = target[0]
    output_distance[target_id] = target_dis
    for i in adjacency_list[target_id]:
        if i[1] + target_dis < output_distance[i[0]]:
            heapq.heappush(distance, ((i[1] + target_dis, i[0])))
    checked_set.add(target_id)
    
for dis in output_distance:
    if dis == math.inf:
        print('INF')
    else:
        print(dis)

Solution (Python):
icase=0
if icase==0:
    vv,e,r=map(int,input().split())
    g=[[] for i in range(vv)]
    for i in range(e):
        si,ti,di=map(int,input().split())
        g[si].append((ti,di))
elif icase==1:
    vv,e,r=4,5,0
    g = [[] for _ in range(vv)]
    g[0]=[(1,1),(2,4)]
    g[1]=[(2,2),(3,5)]
    g[2]=[(3,1)]

elif icase==2:
    vv,e,r=4,6,1
    g = [[] for _ in range(vv)]
    g[0]=[(1,1),(2,4)]
    g[1]=[(2,2)]
    g[2]=[(0,1)]
    g[3]=[(1,1),(2,5)]


from heapq import heappop,heappush

q=[]
heappush(q,(0,r)) 

inf=float("INF")
dist=[inf]*vv
dist[r]=0
while len(q)>0:
    dd,state = heappop(q)

    for v,dv in g[state]:

        if dist[v]>dist[state]+dv:
            dist[v]=dist[state]+dv
            heappush(q,(dist[v],v))


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

Solution (Python):
from heapq import heappop,heappush

def main():
    inf=float("inf")
    v,e,r=map(int,input().split())

    con=tuple([] for _ in range(v))
    for i in range(e):
        s,g,w=map(int,input().split())
        con[s].append((w,g))

    weight=[inf]*v
    fixed=[0]*v
    weight[r]=0
    fixed[r]=1
    work=[]
    for x in con[r]:
        heappush(work,x)
        weight[x[1]]=x[0]

    while work:
        mn=heappop(work)
        
        if fixed[mn[1]] : continue
        fixed[mn[1]]=1
        for x in con[mn[1]]:
            if fixed[x[1]] : continue
            if mn[0]+x[0]<weight[x[1]]:
                weight[x[1]]=mn[0]+x[0]
                heappush(work,(mn[0]+x[0],x[1]))
    
    for i in range(v):
        if weight[i]==inf : print("INF")
        else : print(weight[i])

main()

Solution (Python):
import heapq
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])
    for i,j in enumerate(used):
        if j:
            d[i]=-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])
for i in dijkstra_heap(r,edge):
    if i==-1:
        print('INF')
    else:
        print(i)

Solution (Python):
vn, en, r = map(int,input().split())

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

D0 = [float("inf") for i in range(vn)]

import heapq
D0[r] = 0
D = [(0,r)]
heapq.heapify(D)
count = 0
while True:
    v = -1
    
    if not D:
        break
    new_c, new_v = heapq.heappop(D)
    if D0[new_v] < new_c:
        continue
    D0[new_v] = new_c
    for t,d in cost[new_v]:
        if D0[t] > new_c+d:
            heapq.heappush(D,(new_c+d,t))
            D0[t] = new_c+d

    count += 1

for i in range(vn):
    if not D0[i] == float("inf"):
        print(D0[i])
        continue
    print("INF")

Solution (Python):
from heapq import heappush,heappop
INF=10**18
n,m,r=map(int,input().split())
e=[[] for _ in range(n)]
d=[INF]*n
for i in range(m):
  a,b,c=map(int,input().split())
  e[a].append((b,c))
q=[]
heappush(q,(0,r))
d[r]=0
while q:
  dist,node=heappop(q)
  for to,cost in e[node]:
    if d[to]>cost+dist:
      d[to]=cost+dist
      heappush(q,(d[to],to))
for i in d:
  if i!=INF:print(i)
  else:print('INF')

Solution (Python):


import heapq

n,m,r = map(int,input().split())
edge = [[] for i in range(n)]


for i in range(m):
    u,v,a = map(int,input().split())
    edge[u].append([a,v])

inf = 1145141919810364364
start = 10**15

d = [inf] * n
used = [False] * n
d[r] = 0
used[r] = True
lis = []
    
for k,l in edge[r]:
    heapq.heappush(lis,k*(10**6)+l)
        
while lis:
    minedge = heapq.heappop(lis)
        
    if used[minedge%(10**6)]:
        continue
 
    v = minedge%(10**6)
    d[v] = minedge//(10**6)
    used[v] = True
 
    for q in edge[v]:
        if not used[q[1]]:
            heapq.heappush(lis,(q[0]+d[v])*(10**6)+q[1])
            
for i in d:
    if i >= inf:
        print("INF")
    else:
        print(i)

Solution (Python):
import heapq


def main():
    V, E, r = map(int, input().split())
    G = [[] for _ in range(V)]
    P = [1e10]*V
    for _ in range(E):
        s, t, d = map(int, input().split())
        G[s].append((d, t))

    q = []
    heapq.heapify(q)
    heapq.heappush(q, (0, r))
    fixed = [0]*V
    while q:
        v = heapq.heappop(q)
        if P[v[1]] > v[0]:
            P[v[1]] = v[0]
        fixed[v[1]] += 1
        for g in G[v[1]]:
            if not fixed[g[1]]:
                dist = g[0] + P[v[1]]
                P[g[1]] = dist
                heapq.heappush(q, (dist, g[1]))

    for p in P:
        if p == 1e10:
            print("INF")
        else:
            print(p)


if __name__ == '__main__':
    main()

Solution (Python):









import os
import sys


import heapq


def main():
    V, E, r = map(int, input().split())
    distance = [float("inf")]*V
    distance[r] = 0
    path = [[] for _ in range(V)]
    for _ in range(E):
        s, t, d = map(int, input().split())
        path[s].append([d, t])
    Q = [[0, r]]
    while Q:
        _, u = heapq.heappop(Q)
        for dis, v in path[u]:
            if distance[u]+dis < distance[v]:
                distance[v] = distance[u]+dis
                heapq.heappush(Q, [dis, v])
    distance = [dis if dis != float("inf") else "INF" for dis in distance]
    for dis in distance:
        print(dis)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import heapq

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

    dist = dijkstra_heap(r)
    for res in dist:
        print("INF" if res == f_inf else res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import heapq
V,E,r = map(int,input().split())
adj = [ [] for _ in range(V) ]

for _ in range(E):
  u,v,w = map(int,input().split())
  adj[u].append((v,w))

def dijkstra():
  dist = [float('inf')] * V
  dist[r] = 0
  visited = [False] * V

  pq = [(0,r)]
  while pq:
    w,n = heapq.heappop(pq)
    visited[n] = True

    for nei,wei in adj[n]:
      if visited[nei]: continue
      if w+wei < dist[nei]:
        dist[nei] = w+wei
        heapq.heappush(pq, (w+wei, nei))

  return dist

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

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

vertex = [{'cost': float('inf'), 'dest': []} for _ in range(v)]
vertex[r]['cost'] = 0

for _ in range(e):
    v_id, dest, cost = map(int, input().split())
    vertex[v_id]['dest'].append((dest, cost))

import heapq

q = []
heapq.heapify(q)
heapq.heappush(q, (0, r))

while len(q) != 0:
    distance, v = heapq.heappop(q)

    if vertex[v]['cost'] < distance:
        continue

    for dest in vertex[v]['dest']:
        if vertex[dest[0]]['cost'] > vertex[v]['cost'] + dest[1]:
            c = vertex[v]['cost'] + dest[1]
            vertex[dest[0]]['cost'] = c
            heapq.heappush(q, (c, dest[0]))

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

Solution (Python):
from heapq import *
import sys
I=sys.stdin.readlines()
V,E,r=map(int,I[0].split())
s,t,d=0,0,0
G=[[] for i in range(V)]
for i in range(E):
  s,t,d=map(int,I[i+1].split())
  G[s].append((t,d))
D=[0]*V
INF=10**9+1
def ijk(s):
  global V,D,G,INF
  Q=[]
  heapify(Q)
  for i in range(V):
    D[i]=INF
  D[s]=0
  v,p,e=0,0,0
  heappush(Q,(0,s))
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e[0]]>D[v]+e[1]:
        D[e[0]]=D[v]+e[1]
        heappush(Q,(D[e[0]],e[0]))

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

Solution (Python):
from collections import deque
V, E, R = map(int, input().split())
inf = float('inf')
graphs = [[] for _ in range(V)]

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

start_point = R

dps = [inf for _ in range(V)]
dps[R] = 0

queue = deque([[R, 0]])
while queue:
    now_point, prev_cost = queue.popleft()
    if dps[now_point] < prev_cost:
        continue
    for next_point, cost in graphs[now_point]:
        if dps[next_point] < prev_cost + cost:
            continue
        dps[next_point] = prev_cost + cost
        queue.append([next_point, prev_cost + cost])

for ans in dps:
    if ans == inf:
        print("INF")
    else:
        print(ans)

Solution (Python):
V,E,r = map(int,input().split())
g=[]
for i in range(E):
    s,t,d= map(int,input().split())
    g.append([s,t,d])
inf= 1001001001
dd= [inf]*V 

dd[r]=0
for i in range(V):
    update=0
    for s,t,d in g:
        if dd[t]> dd[s]+d:
            dd[t]= dd[s]+d
            update+=1
    if update==0:
        break
for i in dd:
    if i==inf:
        print("INF")
    else:
        print(i)

Solution (Python):
inf=1001001001
nv,ne,r=map(int,input().split())
d=[inf]*nv
d[r]=0
e=[]
for i in range(ne):
  e.append(list(map(int,input().split())))
for i in range(nv-1):
  flg=False
  for j in e:
    if d[j[1]]>d[j[0]]+j[2]: flg=True
    d[j[1]]=min(d[j[1]],d[j[0]]+j[2])
  if not(flg): break
for i in range(nv):
  print('INF' if d[i]==inf else d[i])

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from heapq import heapify,heappop,heappush
def dijkstra(G,s = 0): 
    n = len(G)
    dist = [INF] * n
    dist[s] = 0
    q = [(0,s)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for e,cost in G[v]:
            if dist[e] > dist[v] + cost:
                dist[e] = dist[v] + cost
                heappush(q,(dist[e],e))
    return dist

def main():
    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))
    
    dist = dijkstra(G,s = r)
    print('\n'.join(map(lambda x:'INF' if x == INF else str(x),dist)))
if __name__ == '__main__':
    main()

Solution (Python):
import heapq
V,E,r = list(map(int,input().split()))
STD = [list(map(int,input().split())) for _ in range(E)]

G = {i:[] for i in range(V)}
for std in STD:
    G[std[0]].append([std[1],std[2]])

dist = [float('inf')] * V
que = [(0, r)]
dist[r] = 0
while que:
    c, v = heapq.heappop(que)
    if dist[v] < c:
        continue
    for t, cost in G[v]:
        if dist[v] + cost < dist[t]:
            dist[t] = dist[v] + cost
            heapq.heappush(que, (dist[t], t))
for cost in dist:
    if cost == float('inf'):
        print('INF')
    else:
        print(cost)