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
s0 t0 d0
s1 t1 d1
:
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.

si and ti  represent source and target vertices of i-th edge (directed) and di represents the cost of the i-th edge.

Output

Print the costs of SSSP in the following format.

c0
c1
:
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 ≤ di ≤ 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



Sample input:
4 5 0
0 1 1
0 2 4
1 2 2
2 3 1
1 3 5


Sample output:
0
1
3
4

Submission status: Accepted

Solution code:
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はノードごとの最小コストを格納したリスト
    '''
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [False] * n #True:未確定
    d[s] = 0
    used[s] = True
    edgelist = []
    # 始点がスタートになってるedgeをヒープキューに追加
    for e in node_edges[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        # ヒープキューからコスト最小のedgeをpop
        # heappopは要素リストの0要素目で最小を管理する
        minedge = heapq.heappop(edgelist)
        # 該当edgeの行き先が確定済みになってなければこれを通って処理が続く
        if used[minedge[1]]:
            continue
        v = minedge[1]
        # 該当edgeの行き先のコストを更新
        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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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     #current_node
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]))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heappushpop, heapreplace, heapify

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


#edge_listに各辺の情報を格納する
#無向ver
edge_list = [[] for i in range(n)]
for _ in range(e):
    s, t, u = map(int, input().split())
    edge_list[s].append([u, t])

    #これは、グラフの入力方法によって必要かどうか変わってくるので注意！！！(有向グラフの場合いらない）
    #edge_list[t].append([u, s])


#隣接行列及びスタートを与えると、各頂点までの最短経路を算出するダイクストラ関数
def dijkstra(edges, start):
    #startの点から各頂点までの最短距離
    d = [float("inf")] * n
    used = [False] * n
    d[start] = 0
    used[start] = True
    #各ノードへのstartからのcostを記録するlistを導入
    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
'''

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)
        # 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 dist:
        print('INF' if i==INF else i)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
from sys import stdin
import math
import heapq
#V:num of vertices
#E: num of edges
#r: start vertex
V, E, r = map(lambda x: int(x), stdin.readline().split(' '))

#create adjacency_list
adjacency_list = [[] for x in range(V)] #size 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)

Submission status: Accepted

Solution code:
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)]
#ans:0 1 3 4
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)]
#ans:3 0 2 INF

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)
#    print("dd:",dd,"state:",state,"q:",q)
    for v,dv in g[state]:
#        print("v:",v,"dv:",dv,"g[state]:",g[state],"parent[v]:",parent[v])
        if dist[v]>dist[state]+dv:
            dist[v]=dist[state]+dv
            heappush(q,(dist[v],v))
#            print(" state:",state,"v:",v,"dist[v]",dist[v])

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

Submission status: Accepted

Solution code:
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)
        #print(mn,weight)
        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()

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    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()) #n:頂点数　w:辺の数
edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
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)

Submission status: Accepted

Solution code:
vn, en, r = map(int,input().split())
# cost = [[float("inf") for _ in range(vn)] for __ in range(vn)] #これだとすごいメモリを食う
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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
#大工

import heapq

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

#aは辺の重み、u,vは辺の情報
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	dijkstra
# CreatedDate:  2020-07-07 00:05:59 +0900
# LastModified: 2020-07-07 00:27:43 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
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()

Submission status: Accepted

Solution code:
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):
        # 始点sから各頂点への最短距離
        d = [f_inf] * n
        used = [True] * n  # True:未確定
        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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

from heapq import heapify,heappop,heappush
def dijkstra(G,s = 0): #sを始点とした最短経を求める
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
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

# map(int, input().split())
# list(map(int, input().split()))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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)]
# cost = [[m for _ in range(V)] for _ in range(V)]
for i in range(E):
    s,t,d = map(int, input().split())
    g[s].append((t, d))
    # cost[s][t] = d

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

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
from heapq import *
import sys
input = sys.stdin.readline
INF = 10 ** 18                                          # 大きい数字

def dijkstra(V, E, G, s):                               # V:頂点数 E:辺の数 G: 隣接する頂点とその重さのリスト s:スタート地点
    d = [INF]*V                                         # 各頂点までの最短距離
    d[s] = 0                                            # 自身への距離は0
    next_set = [(0, s)]                                 # 次に進む候補の頂点と、"スタート地点"からその頂点まで進む距離
                                                        # 始めはスタート地点からスタート地点なので、距離は0
                                                        # heqpq の比較のための key は第一引数である点に注意（ =　heappush(heapq, (key,value))　）
    while next_set:
        dist, p = heappop(next_set)                     # 近いところから順に確定させていく必要があるため、heappop を用いる
        if d[p] < dist:
            continue
        for q, cost in G[p]:                            # p と隣接する点 q と p-q 間の距離
            temp_d = dist + cost                        # スタート地点から p を介して q まで行った時の距離
            if temp_d < d[q]:                           # q まで行く最小距離の更新
                d[q] = temp_d
                heappush(next_set, (temp_d, q))         # q を介して他の頂点に行く可能性を考える。q に行くまでの最短距離が明らかになっている点が重要
    return d

#####( main )#########################################################################################################################

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-1].append((q-1, dist))
    # G[q-1].append((p-1, dist))                          # 有効グラフの場合、コメントアウトする

    G[p].append((q, dist))                            # デクリメントが不要な場合はコメントアウトを消す
    # G[q].append((p, dist))

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)
    #print(q,now,distance)
    
    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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
#!python3

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