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:
from heapq import *

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

dist = [10**18]*V
dist[r] = 0
pq = []
# heapの要素 => (重み、頂点)
heappush(pq, (dist[r], r))

while pq:
    d, v = heappop(pq)

    if dist[v] < d:
        continue

    for w, nv in graph[v]:
        if dist[nv] > dist[v] + w:
            dist[nv] = dist[v] + w
            heappush(pq, (dist[nv], nv))


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

Submission status: Accepted

Solution code:
from heapq import heappush,heapify,heappop
INF = 10**10

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

es=[[] for _ in range(n)] # es[i] = (頂点iの(隣接する頂点,コスト)の組)
d = [INF]*n # 頂点sからの最短距離

# 入力
for i in range(m):
    a,b,c = map(int,input().split())
    es[a].append((b,c))


def dijkstra(s):
    v = -1
    que = [(0,s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que, (d[e[0]], e[0])) 
dijkstra(r)

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

Submission status: Accepted

Solution code:
V, E, r = map(int, input().split())
graph = {i:{} for i in range(V)}
visit = [False for _ in range(V)]
min_d = [(10**18, i) for i in range(V)]
distance = [10**18 for i in range(V)]
import heapq

for i in range(E):
    n1, n2, c = map(int, input().split())
    graph[n1][n2] = c

def dijkstra(s):
    distance[s] = 0
    min_d[s] = (0, s)
    heapq.heapify(min_d)
    while len(min_d):
        m, idx = heapq.heappop(min_d)
        if visit[idx]==True:
            continue
        distance[idx] = m
        visit[idx] = True
        for j in graph[idx].keys():
            heapq.heappush(min_d, (distance[idx]+graph[idx][j], j))
    return distance

min_d = dijkstra(r)
for m in min_d:
    if m==10**18:
        print('INF')
    else:
        print(m)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq as hq

class Dijkstra:
    def __init__(self, node_size, inf):
        self.node_size = node_size
        self.inf = inf
        self.edges = [[] for _ in range(node_size)]
        self.dist = [inf for _ in range(node_size)]

    def add_edge(self, start, end, cost):
        self.edges[start].append((end, cost))

    def solve(self, init_node):
        self.dist[init_node] = 0
        init_dist = 0
        heap = []
        hq.heapify(heap)
        hq.heappush(heap, (init_node, init_dist))

        while heap:
            cur_node, cur_dist = hq.heappop(heap)
            for next_node, cost in self.edges[cur_node]:
                if cost + cur_dist < self.dist[next_node]:
                    self.dist[next_node] = cost + cur_dist
                    hq.heappush(heap, (next_node, cost + cur_dist))
        return self.dist

V, E, init_node = map(int, input().split())
INF = 10 ** 10

dk = Dijkstra(V, INF)

for _ in range(E):
    s, t, d = map(int, input().split())
    dk.add_edge(s, t, d)

result = dk.solve(init_node)

for res in result:
    if res == INF:
        print("INF")
    else:
        print(res)

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline

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

################################
n,w,s = 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()) #0-indexed
    edge[x].append([z,y])
for i in dijkstra_heap(s,edge):
    if i==10**20:
        print('INF')
    else:
        print(i)

Submission status: Accepted

Solution code:
import heapq

inf = 10000000000

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

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

d = [inf]*n

d[r] = 0
pq = [[0,r]]
heapq.heapify(pq)
while len(pq):
    pre = heapq.heappop(pq)
    a,b = pre[0],pre[1]

    if d[b]<a:continue

    for i in range(len(e[b])):
        next_index = e[b][i][0]
        next_cost = d[b]+e[b][i][1]
        if next_cost<d[next_index]:
            d[next_index] = next_cost
            heapq.heappush(pq,[next_cost,next_index])

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

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline

class Node:
    def __init__(self):
        self.link = []
        self.costs = []
        self.check = False
        self.ans = -1

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

    nodes = [Node() for i in range(V)]

    for i in range(E):
        s, t, d = map(int, input().split())
        nodes[s].link.append(t)
        nodes[s].costs.append(d)
    
    q = []
    heapq.heappush(q, (0, r))
    while len(q) > 0:
        cost, num = heapq.heappop(q)
        # print(cost, num)
        node = nodes[num]
        if node.check:
            continue
        node.check = True
        node.ans = cost
        for next_num, p_cost in zip(node.link, node.costs):
            if not nodes[next_num].check:
                heapq.heappush(q, (cost + p_cost, next_num))
    
    for i in range(V):
        print(nodes[i].ans if nodes[i].ans != -1 else "INF")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys

sys.setrecursionlimit(10 ** 5 + 10)


# input = sys.stdin.readline

def resolve():
    from heapq import heappush, heappop

    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))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する

    INF = 10 ** 10

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける
        
        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    for i in dijkstra(V, g, r):
        print(i if i < INF else "INF")


resolve()

Submission status: Accepted

Solution code:
#=============================================================================
# ダイクストラ法
#=============================================================================
import heapq
N,M,s=map(int,input().split())
Graph=[[] for _ in range(N+1)]
dig=["INF" for _ in range(N+1)]
see=[False for _ in range(N+1)]

for _ in range(M):
    a,b,w=map(int,input().split())
    Graph[a].append([w,b])
#    Graph[b].append([w,a])

pq=[]
#s=0
dig[s]=0
see[s]=True
for nv in Graph[s]:
    heapq.heappush(pq,nv)

while len(pq):
    v=heapq.heappop(pq)
    if see[v[1]]:
        continue
    see[v[1]]=True
    dig[v[1]]=v[0]
    for nv in Graph[v[1]]:
        if not see[nv[1]]:
            heapq.heappush(pq,[dig[v[1]]+nv[0],nv[1]])

for i in range(N):
    print(dig[i])

Submission status: Accepted

Solution code:
import heapq

n_vertex, n_edge, start = [int(i) for i in input().split()]
min_costs = [float("inf")] * n_vertex
min_costs[start] = 0
adj_list = {i: set() for i in range(n_vertex)}
for _ in range(n_edge):
    f, t, c = [int(i) for i in input().split()]
    # to, cost
    adj_list[f].add((t, c))

# cost, pos
heap = [(0, start)]
while heap:
    cost, pos = heapq.heappop(heap)
    for next_pos, weight in adj_list[pos]:
        if cost + weight >= min_costs[next_pos]:
            continue
        min_costs[next_pos] = cost + weight
        heapq.heappush(heap, (min_costs[next_pos], next_pos))

for cost in min_costs:
    print(cost if cost < float("inf") else "INF")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,r = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        v[a].append((b,c))
    d = [float("inf")]*n
    d[r] = 0
    q = [(0,r)]
    while q:
        dx,x = heappop(q)
        for y,c in v[x]:
            nd = dx+c
            if nd < d[y]:
                d[y] = nd
                heappush(q,(nd,y))
    for i in d:
        if i == float("inf"):
            print("INF")
        else:
            print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline


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
  

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

Submission status: Accepted

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


def dijkstra1(V, source):
    # O(ElogV)

    n = len(V)
    inf = float("inf")
    dist = [inf] * n
    dist[source] = 0
    q = [(0, source)]

    while q:
        cost, u = heappop(q)
        if dist[u] < cost:
            continue
        for c, v in V[u]:
            if dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
                heappush(q, (dist[v], v))

    return dist

def dijkstra2(V, source):
    # O(V^2)

    n = len(V)
    inf = float("inf")
    used = [False] * n
    dist = [inf] * n
    dist[0] = 0
    
    for _ in range(n):
        c1, u = min([(dist[i], i) for i in range(n) if not used[i]])
        used[u] = True
        for c2, v in V[u]:
            if v==u: continue
            dist[v] = min(dist[v], c1+c2)
    return dist


if __name__ == "__main__":
    V, E, r = map(int, input().split())
    inf = float("inf")
    costs = {i:[] for i in range(V)}
    
    for _ in range(E):
        s, t, d = map(int, input().split())
        costs[s].append((d, t))

    for i in dijkstra1(costs, r):
        print(i if i!=inf else "INF")

Submission status: Accepted

Solution code:
import sys,queue
INF = 10**20
def LI(): return [int(x) for x in sys.stdin.readline().split()]

V,E,r = LI()
dist = [[] for _ in range(V)]
for _ in range(E):
    a,b,d = LI()
    dist[a].append((b,d))

short = [INF for _ in range(V)]
short[r] = 0
q = queue.PriorityQueue()

q.put((0,r))
while not q.empty():
    dt,n = q.get()
    if dt > short[n]:
        continue
    for p,d in dist[n]:
        if short[n] + d < short[p]:
            short[p] = short[n] + d
            q.put((short[p],p))
for i in short:
    print (i if i < INF else 'INF')

Submission status: Accepted

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


if __name__ == '__main__':
    V_n, E_n, s = map(int, input().split())
    route_map = [dict() for _ in range(V_n)]

    for i in range(E_n):
        u, v, a = map(int, input().split())
        u, v = u, v
        route_map[u][v] = a

    # 返回从起点到每个顶点的最短距离的列表
    dijkstra_result = Dijkstra(route_map, s).execute()

    for v in dijkstra_result:
        if v == float('inf'):
            print('INF')
        else:
            print(v)

Submission status: Accepted

Solution code:
#AOJ GRL_1_A
import sys
input = sys.stdin.readline
from heapq import *

def dijkstra(sta):
    dist = [10**18]*V
    dist[sta] = 0
    pq = []
    heappush(pq, (dist[sta], sta))
    
    while pq:
        d, v = heappop(pq)
        
        if dist[v]<d:
            continue
        
        for nv, w in G[v]:
            if dist[nv]>dist[v]+w:
                dist[nv] = dist[v]+w
                heappush(pq, (dist[nv], nv))
    
    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)

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

Submission status: Accepted

Solution code:
import heapq

num_V, num_E, r = map(int,input().split())
E = [[] for _ in range(num_V)]
for _ in range(num_E):
	ts,tt,td = map(int ,input().split())
	E[ts].append([tt,td])

q = []
heapq.heappush(q,[0,r])
flg = [-1] * num_V

while q:
	cd, cp = heapq.heappop(q)
	if flg[cp] == -1:
		flg[cp] = cd
	else:
		continue

	for np, dist in E[cp]:
		if flg[np] != -1:
			continue
		
		heapq.heappush(q,[cd+dist, np])

for d in flg:
	if d == -1:
		print('INF')
	else:
		print(d)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect
import heapq

MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

V, E, r = map(int, input().split())
std = [list(map(int, input().split())) for _ in range(E)]


def bellman_to_dijkstra(n, std):
    vertices_info = [[] for _ in range(n)]
    for edge in std:
        vertices_info[edge[0]].append([edge[1], edge[2]])
    return vertices_info


def dijkstra(n, vertices_info, r):
    weight = [INF for i in range(n)]
    weight[r] = 0
    vertices_index = []
    heapq.heappush(vertices_index, [r, 0])
    while len(vertices_index) > 0:
        u = heapq.heappop(vertices_index)
        for v in vertices_info[u[0]]:
            if u[1] + v[1] < weight[v[0]]:
                weight[v[0]] = u[1] + v[1]
                heapq.heappush(vertices_index, [v[0], weight[v[0]]])
    return weight


ans = dijkstra(V, bellman_to_dijkstra(V, std), r)
for i in ans:
    if i == INF:
        print("INF")
    else:
        print(i)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint
from heapq import heappop, heappush

V, E, r = map(int, sys.stdin.readline().strip().split())
edges = [[] for _ in range(V)]
for _ in range(E):
    s, t, d = map(int, sys.stdin.readline().strip().split())
    edges[s].append((t, d))
# pprint(edges)

dist = [float("inf") for _ in range(V)]
prev = [None] * V

q = []
dist[r] = 0
heappush(q, (dist[r], r))
while q:
    du, u = heappop(q)
    # print(u, du)
    if dist[u] < du:
        continue

    for v, weight in edges[u]:
        alt = du + weight
        if dist[v] > alt:
            dist[v] = alt
            prev[v] = u
            heappush(q, (alt, v))

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

Submission status: Accepted

Solution code:
import heapq

def dijkstra(start, edge, n):

    dist = [float('inf')] * n
    dist[start] = 0

    pq = [(dist[start], start)]

    while len(pq):
        d, frm = heapq.heappop(pq)
        if dist[frm] < d:
            continue
        for to, cost in edge[frm]:
            if dist[frm] + cost < dist[to]:
                dist[to] = dist[frm] + cost
                heapq.heappush(pq, (dist[to], to))

    return dist


if __name__ == '__main__':
    
    n, m, r = map(int, input().split())
    edge = [[] for _ in range(n)]
    for i in range(m):
        x, y, d = map(int, input().split())
        edge[x].append((y, d))

    dist = dijkstra(r, edge, n)

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

Submission status: Accepted

Solution code:
class lheapq():
    # 最小値を取り出す優先度付きキュー
    def __init__(self, p):
        self.l = []
        if p:
            for sp in p:
                self.heappush(sp)

    def heappush(self, a):
        n = len(self.l)
        self.l.append(a)
        t = n
        while t != 0:
            if self.l[t][1] < self.l[(t-1)//2][1]:
                self.l[t], self.l[(t-1)//2] = self.l[(t-1)//2], self.l[t]
                t = (t-1)//2
            else:
                break

    def heappop(self):
        n = len(self.l)
        if n == 0:
            return (-1, 0)
        if n == 1:
            return self.l.pop()
        ret = self.l[0]
        self.l[0] = self.l.pop()
        n -= 1
        t = 0
        while t < n:
            child1 = t*2+1
            child2 = t*2+2
            if child1 >= n:
                break
            elif child2 >= n:
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t], self.l[child1] = self.l[child1], self.l[t]
                    t = child1
                else:
                    break
            else:
                if self.l[child2][1] < self.l[child1][1]:
                    child1, child2 = child2, child1
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t], self.l[child1] = self.l[child1], self.l[t]
                    t = child1
                elif self.l[t][1] > self.l[child2][1]:
                    self.l[t], self.l[child2] = self.l[child2], self.l[t]
                    t = child2
                else:
                    break
        return ret

    def isnotblank(self):
        if self.l:
            return True
        else:
            return False


def dijkstra(s, N, e):
    INF = "INF"
    res = [INF for _ in range(N)]
    q = lheapq([(s, 0)])
    while q.isnotblank():
        while q.isnotblank():
            des, dis = q.heappop()
            if res[des] == INF:
                res[des] = dis
                break
        for se in e[des]:
            if res[se[0]] == INF:
                q.heappush((se[0], se[1]+res[des]))
    return res


N, M, S = map(int, input().split())
g = [[] for _ in range(N)]
for j in range(M):
    a, b, c = map(int, input().split())
    g[a].append((b, c))
print("\n".join(map(str, dijkstra(S, N, g))))

Submission status: Accepted

Solution code:

#重みのないグラフでの最短経路問題
#隣接リストと始点を与えると始点からの距離のリストを返す
from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                q.append(nex)

    return ret


#重みがあるグラフの最短経路問題
#隣接リストは[隣接点,コスト]で入っていること
#負の重みの辺があってはダメ
#連結じゃないと遅くなる

import heapq
def Dijkstra(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    end_flag = [False] * len(lis)
    end_num = 0
    
    q = [[0,start]]

    while len(q) > 0:

        ncost,now = heapq.heappop(q)

        if end_flag[now]:
            continue

        end_flag[now] = True
        end_num += 1

        if end_num == len(lis):
            break

        for nex,ecost in lis[now]:

            if ret[nex] > ncost + ecost:
                ret[nex] = ncost + ecost
                heapq.heappush(q , [ret[nex] , nex])

    return ret


#設定
#One_OriginがTrue場合は0オリジンに直す
#TreeFlagがTrueの時はNのみ入れる。Falseでは頂点数Nと辺数Mを入力。
#Edge_costがTrueならば辺に重みがある。それ以外は常に1になる
#Non_Directなら無向グラフになる
#lisは隣接リスト, コストが存在しない場合隣接番号が直接入る
#存在する場合は[頂点,コスト]のリストが入る

One_Origin = False
Tree_Flag = False
Edge_Cost = True
Non_Direct = False

#input N (& M)
if Tree_Flag:
    N = int(input())
    EDGES = N-1
else:
    N,M,r = map(int,input().split())
    EDGES = M

uvc = [] #Edge_list and costs
lis = [ [] for i in range(N) ] #neighbor list


for i in range(EDGES):

    if Edge_Cost:
        u,v,c = map(int,input().split())
    else:
        u,v = map(int,input().split())

    if One_Origin:
        u -= 1
        v -= 1

    if Edge_Cost:
        uvc.append([u,v,c])
        lis[u].append([v,c])

        if Non_Direct:
            lis[v].append([u,c])

    else:
        uvc.append([u,v,1])
        lis[u].append(v)

        if Non_Direct:
            lis[v].append(u)

dis = Dijkstra(lis,r)

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

Submission status: Accepted

Solution code:
import heapq

INF = 10**9+1

def solve():
  n_V,n_E,r = map(int, input().split())
  graph = {v:[] for v in range(n_V)}
  for _ in range(n_E):
    u,v,w = map(int, input().split())
    graph[u].append((v,w))

  min_distances = [INF]*n_V; min_distances[r] = 0

  prev = [None for _ in range(n_V)]
  # (d(u),u)
  queue = [(min_distances[v], v) for v in range(n_V)]
  heapq.heapify(queue)

  while queue:
    _, dom = heapq.heappop(queue)
    for cod, edge_weight in graph[dom]:
      if min_distances[cod] > min_distances[dom] + edge_weight:
        min_distances[cod] = min_distances[dom] + edge_weight
        prev[cod] = dom
        heapq.heappush(queue, (min_distances[cod], cod))

  for d in min_distances:
    print(d if d < INF else 'INF')


solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
'''
所要時間は、分位であった。
'''


# ライブラリのインポート
#import re
import sys
input = sys.stdin.readline
import heapq
#import bisect
#import collections
#import math
inf = 10000*100000*10
def main():
    v, e, r = map(int, input().split())
    E = [[] for _ in range(v)]
    for line in sys.stdin:
        tmp = list(map(int,line.strip().split()))
        E[tmp[0]].append([tmp[1],tmp[2]])
    
    D = [inf] * v
    D[r] = 0
    Q = []
    heapq.heappush(Q,(D[r],r))
    while(Q):
        d, u  = heapq.heappop(Q)
        for v,w in E[u]:
            if D[v] > D[u] + w:
                D[v] = D[u] + w
                heapq.heappush(Q, (D[v],v))

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


    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappop,heappush,heapify

class Graph():
    def __init__(self,n,edge,directed=False):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append((e[1],e[2]))
            if not directed:
                self.graph[e[1]].append((e[0],e[2]))
    def dijkstra(self,s,INF=10**18):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0,s)]
        while heap:
            cost,node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj,adjcost in self.graph[node]:
                if dist[node]+adjcost < dist[adj]:
                    dist[adj] = dist[node]+adjcost
                    heappush(heap,(dist[adj],adj))
        return dist

INF = 10**18

import sys
input = sys.stdin.readline

V,E,r = map(int,input().split())
edge = [tuple(map(int,input().split())) for _ in range(E)]

g = Graph(V,edge,True)
D = g.dijkstra(r,INF)

for i in range(V):
    if D[i] == INF: D[i] = 'INF'

print('\n'.join(map(str,D)))

Submission status: Accepted

Solution code:
# GRL_1_A - Single Source Shortest Path
from heapq import heappop, heappush
from typing import List

inf = 1 << 30


def dijkstra(source: int, edges: List[List[List[int]]]) -> List[int]:
    """
    Compute the distance of the shortest path from V_source to each vertex.

    Args:
        source: V_source
        edges: Edges info
    Returns:
        dist: A list of distance from V_source
    """
    edges_count = len(edges)
    dist = [inf] * edges_count
    dist[source] = 0
    undetermined = edges_count - 1  # V_0 is determined in 1-idx graph
    queue = [(0, source)]
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        for next_cost, u in edges[v]:
            if cost + next_cost < dist[u]:
                dist[u] = cost + next_cost
                heappush(queue, (dist[u], u))
        undetermined -= 1
        if not undetermined:
            break
    return dist  # There may be no path from V_source to some vertices.


def main():
    N, M, R, *E = map(int, open(0).read().split())
    edges: List[List[List[int]]] = [[] for _ in range(N)]
    for v, u, cost in zip(*[iter(E)] * 3):
        edges[v].append([cost, u])
    dist = dijkstra(R, edges)
    ans = [i if i < inf else "INF" for i in dist]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
inf = float('inf')
mod = 10**9 + 7

# ダイクストラ法 計算量O(ElogV)
# [引数]: 隣接リスト, 始点
class dijkstra:
    def __init__(self, to:list, start:int):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.dist = [inf] * self.N
        self.dist[start] = 0
        # cnt : 最短経路の数
        self.cnt = [0] * self.N
        self.cnt[start] = 1
        self.pq = [(self.dist[start], start)]

    # distを更新
    def update(self) -> None:
        while self.pq:
            _, v = heappop(self.pq)
            for nv, w in self.to[v]:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    heappush(self.pq, (self.dist[nv], nv))
                if self.dist[nv] == self.dist[v] + w:
                    self.cnt[nv] += self.cnt[v]
                    self.cnt[nv] %= mod

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

DI = dijkstra(to, r)
DI.update()
for d in DI.dist:
    if d == inf:
        print("INF")
    else:
        print(d)

Submission status: Accepted

Solution code:
def shortest_path_faster_algorithm(E, start):
    # ベルマンフォードの更新があるところだけ更新する感じのやつ
    # O(VE) だが実用上高速
    # E は隣接リスト
    # 検証: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4005805#1
    from collections import deque
    inf = float("inf")  # 10**18 は良くない
    N = len(E)
    q = deque([start])
    distance = [inf] * N;  distance[start] = 0
    in_q = [0] * N;        in_q[start] = True
    times = [0] * N;       times[start] = 1
    while q:
        v = q.popleft()
        in_q[v] = False
        dist_v = distance[v]
        for u, cost in E[v]:
            new_dist_u = dist_v + cost
            if distance[u] > new_dist_u:
                times[u] += 1
                if times[u] >= N:  # 負閉路検出
                    distance[u] = -inf
                else:
                    distance[u] = new_dist_u
                if not in_q[u]:
                    in_q[u] = True
                    q.append(u)
    return distance

import sys
def main():
    N, M, r = map(int, sys.stdin.readline().split())
    E = [[] for _ in range(N)]
    for s, t, d in zip(*[iter(map(int, sys.stdin.read().split()))]*3):
        E[s].append((t, d))
    distance = shortest_path_faster_algorithm(E, r)
    for d in distance:
        if d == float("inf"):
            print("INF")
        else:
            print(d)

main()

Submission status: Accepted

Solution code:
import heapq
import string


INF = 1e9


def dijkstra(graph, start=0, goal=None):
    min_cost = [INF for _ in range(len(graph))]
    min_cost[start] = 0
    que = [(0, start)]
    result = INF

    while len(que) > 0:
        cur_cost, cur_node = heapq.heappop(que)
        if goal is not None and cur_node == goal:
            result = cur_cost
            break
        for to, cost in graph[cur_node]:
            new_cost = cur_cost + cost
            if new_cost >= min_cost[to]:
                continue
            min_cost[to] = new_cost
            heapq.heappush(que, (new_cost, to))

    return min_cost


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

    min_cost = dijkstra(graph, r)

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


if __name__ == "__main__":
    main()