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:
import sys
import heapq


class Edge:
    def __init__(self, vertex_to, weight):
        self.vertex_to = vertex_to
        self.weight = weight


class Vertex:
    def __init__(self):
        self.distance = sys.maxsize
        self.fixed: bool = False
        self.edges_from_this_vertex = []


class DijkstraAlgorithm:
    def __init__(self, number_of_vertices):
        self._number_of_vertices = number_of_vertices
        self._number_of_edges = 0
        self._vertices = [Vertex() for _ in range(number_of_vertices)]
        self._priority_queue = []
        heapq.heapify(self._priority_queue)

    def add_vertex(self, from_index, to_index, weight):
        self._vertices[from_index].edges_from_this_vertex.append(Edge(to_index, weight))

    def calculate_shortest_paths(self, start_vertex_index):
        self._vertices[start_vertex_index].distance = 0
        heapq.heappush(self._priority_queue, (self._vertices[start_vertex_index].distance, start_vertex_index))
        while len(self._priority_queue) > 0:
            shortest_vertex_distance, shortest_vertex_index = heapq.heappop(self._priority_queue)
            self._vertices[shortest_vertex_index].fixed = True
            for c_edge in self._vertices[shortest_vertex_index].edges_from_this_vertex:
                if not self._vertices[c_edge.vertex_to].fixed:
                    distance_candidate = shortest_vertex_distance + c_edge.weight
                    if distance_candidate < self._vertices[c_edge.vertex_to].distance:
                        self._vertices[c_edge.vertex_to].distance = distance_candidate
                        heapq.heappush(self._priority_queue, (distance_candidate, c_edge.vertex_to))

    def print(self):
        for c_vertex in self._vertices:
            if c_vertex.distance == sys.maxsize:
                print('INF')
            else:
                print(c_vertex.distance)


def call_dijkstra_algorithm():
    inputs = list(map(int, input().strip().split(' ')))
    number_of_vertices = inputs[0]
    number_of_edges = inputs[1]
    start_vertex_index = inputs[2]
    dijkstra = DijkstraAlgorithm(number_of_vertices)

    for _ in range(number_of_edges):
        inputs = list(map(int, input().strip().split(" ")))
        from_index = inputs[0]
        to_index = inputs[1]
        weight = inputs[2]
        dijkstra.add_vertex(from_index, to_index, weight)

    dijkstra.calculate_shortest_paths(start_vertex_index)
    dijkstra.print()


if __name__ == '__main__':
    call_dijkstra_algorithm()

Submission status: Accepted

Solution code:
import heapq

def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O((E+V)logV)
    """
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    q = [(0, start)]  # q = [(startからの距離, 現在地)]
    while q:
        d, v = heapq.heappop(q)
        if dist[v] < d:
            continue
        for nxt_v, cost in graph[v]:
            if dist[v] + cost < dist[nxt_v]:
                dist[nxt_v] = dist[v] + cost
                heapq.heappush(q, (dist[nxt_v], nxt_v))
    return dist

def main():

    n, m, s = map(int, input().split())
    info = [list(map(int, input().split())) for i in range(m)]
    INF = 10 ** 18

    graph = [[] for i in range(n)]
    for a, b, cost in info:
        graph[a].append((b, cost))

    dist = dijkstra(s, graph)
    for i in range(n):
        if dist[i] == INF:
            print("INF")
        else:
            print(dist[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 入力
Vn, En, r = map(int, input().split())

Ve = [ [] for _ in range(Vn)]

for _ in range(En):
    s, t, c = map(int, input().split())
    Ve[s].append((t,c))

# 初期化
INF = 10**4 * 10**5
dp = [INF] * Vn
dp[r] = 0

# ダイクストラ
from heapq import heappush, heappop

q = [(0, r)]
while q:
    du, u = heappop(q)
    
    for v, dv in Ve[u]:
        if dp[v] > du + dv:
            dp[v] = du + dv
            heappush(q, (du + dv, v))

# 解答
for i in range(Vn):
    if not dp[i] == INF:
        print(dp[i])
    else:
        print("INF")

Submission status: Accepted

Solution code:
n, m, r = map(int, input().split())
#高速化dijkstra
import heapq
def dijkstra_heap(s,edge):
  d = [float("inf")] * n #始点sから各頂点への最短距離
  used = [False] * n
  d[s] = 0
  used[s] = True
  edgelist = []
  #edgelist : (sからの暫定(未確定)最短距離+頂点)
  #edge[s] : sから出る枝の(重み,終点)の配列
  for w,v in edge[s]:
    heapq.heappush(edgelist,w*10**6+v) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    minedge = heapq.heappop(edgelist)
    #minedge : (sからの確定最短距離+頂点)
    v = minedge%10**6
    if used[v]:
      continue
    d[v] = minedge//10**6
    used[v] = True
    for w,u in edge[v]:
      if not used[u]:
        heapq.heappush(edgelist,(d[v]+w)*10**6+u)
  return d

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

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

d = dijkstra_heap(r,edge)
for ans in d:
    if ans==float('inf'):
        print('INF')
    else:
        print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import heapq
INF = float('inf')

# n : 頂点の数 m : 辺の数 r : 始点
n, m, r = [int(x) for x in input().split()]
E = [tuple([int(x) for x in input().split()]) for _ in range(m)]

AL = [[] for _ in range(n)] # 隣接リスト
for i in range(m):
    AL[E[i][0]].append(tuple(E[i][1:]) )  # AL[head] = [(tail, cost), ..., (tail, cost)]

fixed = [False] * n # 重み確定したかどうか
nfixed = 0 # 確定した数
vertex_cost = [INF] * n  # 始点rから各頂点への重み

# 1. 始点に0を書き込む
vertex_cost[r] = 0
H = []  # (cost, vertex)のheap
heapq.heappush(H, (0, r))

i = 0
while(H): # Hが空になるまで
    i += 1
    # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
    u_cost, u = heapq.heappop(H)
    if fixed[u]: continue
    fixed[u] = True
    nfixed += 1

    # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
    #    重みを計算し、書き込まれている値より小さければ更新する
    for v, edge_cost in AL[u]:
        if fixed[v]: continue
        newcost = vertex_cost[u] + edge_cost
        if newcost < vertex_cost[v]:
            vertex_cost[v] = newcost
            heapq.heappush(H, (newcost, v))

    # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
    if nfixed == n: break

for i in range(n):
    if vertex_cost[i] == INF:
        print("INF")
    else:
        print(vertex_cost[i])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
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((d, t))
    # G[t].append((d, s))

dist = [float('inf') for _ in range(v)]

prev = [(0,r)]

while len(prev):
    now = heappop(prev)
    if dist[now[1]] < now[0]:
        continue
    else:
        dist[now[1]] = now[0]
    for nxt in G[now[1]]:
        if dist[nxt[1]] > dist[now[1]] + nxt[0]:
            dist[nxt[1]] = dist[now[1]] + nxt[0]
            heappush(prev,(nxt[0]+dist[now[1]], nxt[1]))
    # print(now,prev,dist)
for i in dist:
    if i ==float('inf'):
        print("INF")
    else:
        print(i)

Submission status: Accepted

Solution code:
#計算量ElogV
V,E,r = map(int,input().split()) #頂点数、辺の数，始点
cost = [[] for _ in range(V)] #cost[u][v]がuからvへの距離
INF = float("inf")
d = [INF]* V #頂点ｒから頂点iへの最短重み距離　　　　　
prev = [-1] * V #最短距離をたどるとき、頂点iの一回前に通る頂点
used = [True]*V #Trueは未確定
for _ in range(E):
    s,t,dd = map(int,input().split())
    cost[s].append([dd,t])
d[r] = 0
used[r] = False
import heapq
Q = []
for e in cost[r]:
    heapq.heappush(Q,e)
while len(Q) != 0:
    dis,v = heapq.heappop(Q)
    if used[v] == False:#すでに確定していたら
        continue
    d[v] = dis
    used[v] = False #確定させる
    for e in cost[v]:
        if used[e[1]] == True:#まだ確定していなかったら
            heapq.heappush(Q,[e[0]+d[v],e[1]])
for k in d:
    if k != INF:
        print(k)
    else:
        print("INF")

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
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((d, t))

dp = [-1] * V

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

while len(q) > 0:
    d, x = heappop(q)
    if dp[x] > -1: continue
    dp[x] = d
    for nd, nt in edge[x]:
        heappush(q, (d+nd, nt))

for i in dp:
    print(i if i > -1 else "INF")

Submission status: Accepted

Solution code:
from heapq import *
def dijkstra(s, n, w, cost):
    #s:始点,n:頂点数,w:辺の数,cost:辺ijの重み
    ans = [float('inf')] * n #最短距離の記録
    d = [[float('inf'), i] for i in range(n)]
    used = [False] * n #一度最短距離を確定した頂点はもう見ない
    ans[s] = 0
    d[s][0] = 0
    heapify(d)

    while d:
        D, V = heappop(d)
        if used[V]:continue
        used[V] = True

        for t, distance in cost[V]:
            ans[t] = min(ans[t], D + distance)
            heappush(d, [ans[t], t])
    return ans

v, e, r = map(int,input().split())
route_list=[[] for i in range(v)]#辺の移動の際のコスト

for i in range(e):
    s,t,d=map(int,input().split())
    route_list[s].append((t,d))
#print(route_list)

ans = dijkstra(r, v, e, route_list)

for i in ans:
    if i == float('inf'):
        print('INF')
    else:
        print(i)

Submission status: Accepted

Solution code:
import heapq

VEr = input().split()
#隣接リスト
V,E,r = int(VEr[0]), int(VEr[1]), int(VEr[2])
List = [[] for i_ in range(V)]
heap = []
result = [float("inf")] * V
for i in range(E):
    s,t,d = map(int,input().split())
    List[s].append([t, d])

result[r] = 0
heapq.heappush(heap, [0,r])
while len(heap) != 0:
    #temp[コスト,]
    temp = heapq.heappop(heap)
    cost = temp[0]
    basyo =temp[1]
    if(cost > result[basyo]):
        continue
    else:
        for i in List[basyo]:
            if(result[i[0]] > result[basyo] + i[1]): 
                result[i[0]] = result[basyo] + i[1]
                heapq.heappush(heap, [result[i[0]] , i[0]])

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

Submission status: Accepted

Solution code:
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([d,t])

def dijkstra(s):
    import heapq
    dist = [float('inf')] * V
    fixed = [False]*V
    dist[s] = 0
    fixed[s] = True
    priority_que = []
    for e in edges[s]:
        heapq.heappush(priority_que,e)

    while len(priority_que):
        edge = heapq.heappop(priority_que)
        if fixed[edge[1]]:
            continue
        v = edge[1]
        dist[v] = edge[0]
        fixed[v] = True
        for ne in edges[v]:
            heapq.heappush(priority_que,[ne[0]+dist[v], ne[1]])
    return dist
dist = dijkstra(r)
for dd in dist:
    if dd == float('inf'):
        print('INF')
    else:
        print(dd)

Submission status: Accepted

Solution code:
import heapq
n, m, r = map(int, input().split())
G = [{} for i in range(n)]
for j in range(m):
    s, t, d = map(int, input().split())
    G[s][t] = d
inf = 10**20
D = [inf for i in range(n)]
D[r] = 0
Q = [(0, r)]
heapq.heapify(Q)
while Q:
    _, x = heapq.heappop(Q)
    for y in G[x].keys():
        if D[x]+G[x][y] < D[y]:
            D[y] = D[x]+G[x][y]
            heapq.heappush(Q, (D[y], y))
for i in range(n):
    if D[i] == inf:
        print('INF')
    else:
        print(D[i])

Submission status: Accepted

Solution code:
import heapq
inf=10**9


def dijkstra():
    V,E,r=map(int,input().split())
    color=["white" for _ in range(V)]
    D=[inf for _ in range(V)]
    M=[[] for _ in range(V)]

    D[r]=0
    color[r]="gray"
    queue=[[0,r]]
    heapq.heapify(queue)

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

    while len(queue)!=0:
        u=heapq.heappop(queue)[1]
        if color[u]=="black":continue
        color[u]="black"

        V=[[i,j] for i,j in M[u] if color[j]!="black"]
        if len(V)>0:
            for i,j in V:
                if D[u]+i<D[j]:
                    D[j]=D[u]+i
                    color[j]="gray"
                    heapq.heappush(queue,[D[j],j])

    return D


D=dijkstra()
for i in D:
    if i==inf:print("INF")
    else:print(i)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10 ** 12

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

graph = [[] for _ in range(V)]
dist_all = [INF] * V
dist_all[r] = 0
for i in range(E):
  start, end, dist1 = map(int, input().split())
  graph[start].append([end, dist1])
  
q = []
heappush(q, (0, r))

while q:
  dist, node = heappop(q)
  for to, cost in graph[node]:
    if(dist_all[to] > dist + cost):
      dist_all[to] = dist + cost
      heappush(q, (dist+cost, to))
  
for i in range(V):
  if(dist_all[i] == INF):
    print('INF')
  else:
    print(dist_all[i])

Submission status: Accepted

Solution code:
import math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools
import bisect

# from operator import mul

sys.setrecursionlimit(100001)
INF = sys.maxsize


# input = sys.stdin.readline

# ===FUNCTION===

def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(sys.stdin.readline())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = sys.stdin.readline().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

queue = []
heapq.heappush(queue, (0,r))
dist_lst[r] = 0

while queue:
    dist, node = heapq.heappop(queue)
    for t, cost in edges_lst[node]:
        if dist_lst[t] > dist+cost:
            dist_lst[t] = dist+cost
            heapq.heappush(queue, (dist_lst[t], t))

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10**18

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

cost = [[] for i in range(V)]
for i in range(E):
    x, y, z = map(int, input().split())
    cost[x].append([y, z])
 
dist_lst = [INF for _ in range(V)]

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

while que:
    dist, node = heappop(que)
    for to, cos in cost[node]:
        if dist_lst[to] > cos+dist:
            dist_lst[to] = cos + dist
            heappush(que, (cos+dist, to))
 
for dist in dist_lst:
    if(dist == INF):
        print("INF")
    else:
        print(dist)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=ja
from heapq import heappop, heappush
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class Dijkstra:
    """
    shortest_distansce(g): startノードからgoalノードまでの最短距離
    shortest_path(g): startノードからgoalノードまでの最短経路
    """
    def __init__(self, graph, start):
        """
        graph: 隣接リストによるグラフ
        start: 始点のノード番号
        """
        self.g = graph
        self.V = len(graph)

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = [float('inf')] * (self.V)
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = [None] * (self.V)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (0, start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if dist_u > self.dist[u]:
                continue
            for v, weight in self.g[u]:
                alt = self.dist[u] + weight
                if alt < self.dist[v] :
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


def main():
    N,_,start,*edge = map(int, read().split())
    
    E = [[] for _ in range(N)]
    for a, b, w in zip(*[iter(edge)]*3):
        E[a].append((b, w))

    dijkstra = Dijkstra(E, start)
    
    for i in range(N):
        d = dijkstra.shortest_distance(i)
        if d == float('inf'):
            print("INF")
        else:
            print(d)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
INF = 1<<60
from heapq import heappush, heappop

V, E, r = map(int, input().split())
G = [[] for _ in range(V)]
for _ in range(E):
    f, t, c = map(int, input().split())
    G[f].append((t, c))

dist = [INF]*V
dist[r] = 0

q = [(0,r)] # cost, root
while q:
    cost, v = heappop(q)
    for to, c in G[v]:
        sum_C = cost + c
        if sum_C < dist[to]:
            dist[to] = sum_C
            heappush(q,(sum_C, to))

for c in dist:
    print(c if c<INF else "INF")

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue # (s,v)-shortest path is already calculated
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]
    
N, M, r = map(int, input().split())
dk = Dijkstra(N)
for _ in range(M):
    a, b, c = map(int, input().split())
    dk.add_edge(a, b, c)
dist = dk.distance(r)
for d in dist:
    if d == float('inf'): print('INF')
    else: print(d)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop, heapify

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

    q = edge[r]
    heapify(q)
    count = V-1

    while count and q:
        c, v = heappop(q)

        if visited[v]: continue

        count -= 1
        visited[v] = True
        dist[v] = c

        for cc, u in edge[v]:
            if not visited[u]: heappush(q, (c+cc, u))
    
    return dist

def main():
    V, E, r = list(map(int, input().split()))

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heapify, heappop, heappush

INF = 10 ** 11 + 1
nV, nE, r = map(int, input().split())
G = defaultdict(list)

for _ in range(nE):
    a, b, c = map(int, input().split())
    G[a].append((b, c))
    # G[b].append((a, c))

# # dijkstra
# r -= 1
# d = dijkstra(r)
# print(d)

d = [INF for _ in range(nV)]
d[r] = 0
queue = [(0, r)]
while queue:
    c, v = heappop(queue)
    # if d[v] < c:
    #     continue
    for u, cost in G[v]:
        if d[v] + cost  < d[u]:
            d[u] = d[v] + cost
            heappush(queue, (d[u], u))

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

def dijkstr(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

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 dijkstr(G,r):
		if i==INF:
			print("INF")
		else:
			print(i)

if __name__=="__main__":main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = float("inf")


def dijkstra(v, st, g):
    dist = [INF] * v
    dist[st] = 0
    hq = [(st, 0)]  # (頂点，重み)
    while hq:
        u, d = heappop(hq)
        if dist[u] < d:
            continue
        for nu, w in g[u]:  # (隣接頂点，重み)
            nw = d + w
            if dist[nu] > nw:
                dist[nu] = nw
                heappush(hq, (nu, nw))
    return dist


def main():
    v, e, st = 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))  # s->tの有向グラフ
    for ans in dijkstra(v, st, g):
        if ans == INF:
            print('INF')
        else:
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

def dijkstra_heap(s):
    d = [float('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,e,r = map(int, input().split())
std = [[int(x) for x in input().split()] for _ in range(e)]
edge = [[] for _ in range(n)]
for s, t, d in std:
    edge[s].append([d, t])
ans = dijkstra_heap(r)
for x in ans:
    if x==float('inf'): print('INF')
    else: print(x)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
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))
PQ = []
INF = float("inf")
dist = [INF]*V
white = 0; gray = 1 ;black = 2
color = [white]*V
heappush(PQ,(0,r))
dist[r] = 0

while PQ:
    md,s = heappop(PQ)
    color[s] = black
    if dist[s] < md: continue
    for t,d in G[s]:
        if color[t] == black: continue
        if dist[t] > dist[s] + d:
            dist[t] = dist[s] + d
            color[t] = gray
            heappush(PQ,(dist[t],t))
    
print("\n".join(map(lambda x:"INF" if x == INF else str(x),dist)))

Submission status: Accepted

Solution code:
import heapq


def dijkstra(start_v, G):
    n = len(G)
    dist = [0 if i == start_v else float("inf") for i in range(n)]

    que = []
    heapq.heappush(que, (0, start_v))

    while que:
        cur_d, cur_v = heapq.heappop(que)
        if dist[cur_v] < cur_d:
            continue
        for adj in G[cur_v]:
            nxt_v, cost = adj
            if dist[cur_v] + cost < dist[nxt_v]:
                dist[nxt_v] = dist[cur_v] + cost
                heapq.heappush(que, (dist[nxt_v], nxt_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))

dist = dijkstra(r, g)
for i in range(v):
    if dist[i] != float("inf"):
        print(dist[i])
    else:
        print("INF")

Submission status: Accepted

Solution code:
import heapq


def dijkstra(s, edge):
    # 始点sから各頂点への最短距離
    dist = [10**20] * N
    used = [False] * N
    dist[s] = 0
    used[s] = True
    edgelist = []
    for a, b in edge[s]:
        # a : 距離, b : 頂点番号
        heapq.heappush(edgelist, a * (10**6) + b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        # まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge % (10**6)]:
            continue
        v = minedge % (10**6)
        dist[v] = minedge//(10**6)
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist, (e[0]+dist[v])*(10**6)+e[1])
    return dist


N, M, r = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(M)]
edge = [[] for _ in range(N)]
for i in graph:
    edge[i[0]].append([i[2], i[1]])

dist = dijkstra(r, edge)
for i in range(N):
    if dist[i] == 10**20:
        print("INF")
    else:
        print(dist[i])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 1e18

# star, goal, 隣接リスト
def dijkstra(st, g):
    n = len(g)
    dis = [INF] * n
    dis[st] = 0
    que = []
    heappush(que,(0,st))

    while que:
        d, u = heappop(que)
        for v, cost in g[u]:
            if dis[v] > d + cost:
                dis[v] = d + cost
                heappush(que,(dis[v],v))
    return dis

def main():
    n, m, st = map(int, input().split())
    g = [[] for _ in range(n)]
    
    for _ in range(m):
        u, v, cost = map(int, input().split())
        g[u].append((v,cost))

    res = dijkstra(st, g)
    for ans in res:
        if ans == INF:
            print("INF")
        else:
            print(ans)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):
    """
    隣接リストによる有向グラフ
    """
    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()

class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """
    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

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

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)

d = Dijkstra(g,r)
ans=d.shortest_distance()
for i in range(n):
    if ans[i]==float("inf"):
        print("INF")
    else:
        print(int(ans[i]))

Submission status: Accepted

Solution code:
import heapq
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))
# print(*G, sep='\n')
dp = [float('inf')] * V
dp[r] = 0
Q = []
heapq.heappush(Q, (0, r))
while len(Q) > 0:
    # print(Q)
    d, v = heapq.heappop(Q)
    if dp[v] < d:
        continue

    for nv, nd in G[v]:
        if dp[nv] > dp[v] + nd:
            dp[nv] = dp[v] + nd
            heapq.heappush(Q, (dp[nv], nv))
# print(dp)
print(*[d if d != float('inf') else 'INF' for d in dp], sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import heapq
from collections import namedtuple

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


edge = namedtuple("edge", ("cost", "to"))
vertex_route = namedtuple("vertex_route", ("routecost", "vertex"))

def main():
    v, e, r = read_list(int)
    edges_of_v = {}
    for _ in range(e):
        s, t, d = read_list(int)
        if s not in edges_of_v:
            edges_of_v[s] = []
        edges_of_v[s].append(edge(d, t))
    
    min_costs = [1 << 33] * v
    que = [vertex_route(0, r)]
    heapq.heapify(que)
    while que:
        route = heapq.heappop(que)
        if min_costs[route.vertex] <= route.routecost:
            continue
        min_costs[route.vertex] = route.routecost
        if route.vertex not in edges_of_v:
            continue
        for e in edges_of_v[route.vertex]:
            if min_costs[e.to] <= e.cost + min_costs[route.vertex]:
                continue
            heapq.heappush(que, vertex_route(e.cost + min_costs[route.vertex], e.to))
    
    for i in range(v):
        if min_costs[i] == 1 << 33:
            print("INF")
        else:
            print(min_costs[i])

if __name__ == "__main__":
    main()