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:
# -*- coding: utf-8 -*-
"""
Created on Sat May 18 23:11:54 2019

@author: maezawa
"""

import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        0-indexedでなくてもよいことに注意
        s = 始点
        return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d
    
v, e, r = list(map(int, input().split()))
graph1 = Dijkstra()
for _ in range(e):
    si, ti, di = list(map(int, input().split()))
    graph1.add(si, ti, di, directed=True)
    
res = graph1.Dijkstra_search(r)
for i in range(v):
    ans = res[i]
    if ans == float('inf'):
        print('INF')
    else:
        print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math

graph = []
# input 
V, E, r = map(int, input().split())
# initialize
lens = [float('inf') for i in range(V)]
lens[r] = 0
# input
for i in range(E) :
    start, desti, distance = map(int, input().split())
    graph.append([start, desti, distance])
    
# judge 
while True :
    # set a flag
    flag = True
    for q in graph :
        # compare the distance 
        if lens[q[1]] > lens[q[0]] + q[2]:
          lens[q[1]] = min(lens[q[1]], lens[q[0]] + q[2])
          flag = False         
    if flag:
      break
# output results 
for item in lens :
    if math.isinf(item):
        print("INF")
    else :
        print(item)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush
from heapq import heappop
from collections import deque


n_V, n_E, r = map(int, input().split())

E = [[] for _ in range(n_V)]
for i in range(n_E):
    v, e, c = map(int, input().split())
    E[v].append((e, c))


D = [sys.maxsize for _ in range(n_V)]
D[r] = 0

h = []
heappush(h, (D[r], r))


while len(h) != 0:
    _, index = heappop(h)

    for e, c in E[index]:
        d = D[index] + c
        if D[e] > d:
            D[e] = d
            heappush(h, (d, e))


for d in D:
    if d == sys.maxsize:
        print('INF')
    else:
        print(d)

Submission status: Accepted

Solution code:
if __name__=='__main__':
    V_MAX = 100000
    E_MAX = 500000
    INF = float('inf')

    v,e,r=(int(x) for x in  input().split())
        
    e_from = []
    e_to = []
    e_cost= []
    dist=[]

    for i in range(e):
        f, t, c=(int(x) for x in  input().split())
        e_from.append(f)
        e_to.append(t)
        e_cost.append(c)

    for i in range(v):
        dist.append(INF)
   
    dist[r] = 0
   
    while True:
        flag = 1
        for i in range(e):
            if (dist[e_from[i]] != INF) and (dist[e_to[i]] > dist[e_from[i]]+e_cost[i]):
                dist[e_to[i]] = dist[e_from[i]] + e_cost[i]
                flag=0

        if flag:
            break
    

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

Submission status: Accepted

Solution code:
import sys
import heapq
MAX_INT = float("Inf")

def find_shortest_path_with_weight(graph,start_v,v_num):
    distance = [MAX_INT]*v_num
    distance[start_v] = 0
    queue = []*v_num
    queue.append((distance[start_v],start_v))
    while True:
        if(len(queue)==0):
            break
        #weight,v = heapq.heappop(queue)
        #queue = sorted(queue,key=lambda k:k[0])
        weight,v = queue.pop(0)
        if(distance[v] < weight):
            continue
        for i,(to,weight) in enumerate(graph[v]):
            if(weight + distance[v] < distance[to]):
                distance[to] = weight + distance[v]
                #queue.append((distance[i],i))
                heapq.heappush(queue,(distance[to],to))
    
    for i in distance:
        if(i < MAX_INT):
            print(i)
        else:
            print("INF")

        
if __name__ == '__main__':
    v_num,e_num,start_v = map(int, input().split())
    # omomituki graph tukuruyo
    graph = [ [] for _ in range(v_num)]
    for i in range(e_num):
        s,t,w = map(int, input().split())
        graph[s].append((t,w))
    find_shortest_path_with_weight(graph,start_v,v_num)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop


class Dijkstra:
    class Edge:
        def __init__(self, end, cost):
            self.to = end
            self.cost = cost

    def __init__(self, node_size, inf):
        self._node = node_size
        self._graph = [[] for _ in range(self._node)]
        self.inf = inf
        self.dist = [self.inf for _ in range(self._node)]

    def add_edge(self, st, ed, cs):
        self._graph[st].append(self.Edge(ed, cs))

    def solve(self, start):
        que = []
        self.dist[start] = 0
        heappush(que, (0, start))
        while que:
            cur_cost, cur_vertex = heappop(que)
            if self.dist[cur_vertex] < cur_cost:
                continue
            for e in self._graph[cur_vertex]:
                if self.dist[e.to] > cur_cost + e.cost:
                    self.dist[e.to] = cur_cost + e.cost
                    heappush(que, (self.dist[e.to], e.to))


if __name__ == '__main__':
    V, E, r = map(int, sys.stdin.readline().split())
    dk = Dijkstra(V, 10 ** 10)
    for i in range(E):
        s, t, d = map(int, sys.stdin.readline().split())
        dk.add_edge(s, t, d)
    dk.solve(r)
    for value in dk.dist:
        if value == dk.inf:
            sys.stdout.write("INF\n")
        else:
            sys.stdout.write("%s\n" % value)

Submission status: Accepted

Solution code:
import heapq


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

    return d


v, e, r = map(int, input().split())
g = [[] for i in range(v)]
for i in range(e):
    s, t, d = map(int, input().split())
    g[s].append((t, d))

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

Submission status: Accepted

Solution code:
import heapq
def dijkstra(start:int):
    """priority_queue ver. O(|E|log|V|)
    """
    global dist # list dist[|V|]
    global edges # 隣接リスト
    dist[start] = 0
    q = [(0,start)] #（暫定的な距離，頂点）
    while q:
        d_cur,cur = heapq.heappop(q)
        if dist[cur] < d_cur: # すでに探索済み
            continue
        for nex,cost in edges[cur]:
            if dist[nex] > dist[cur]+cost:
                dist[nex] = dist[cur]+cost
                heapq.heappush(q, (dist[nex], nex))


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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


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


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

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

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

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

while pq:
    u = heappop(pq)
    if V[u[1]]:
        continue
    for v in G[u[1]]:
        if v.cost + u[0] < D[v.to]:
            D[v.to] = v.cost + u[0]
            heappush(pq, (D[v.to], v.to))
    V[u[1]] = True
#
for d in D:
    print(d if d != float('inf') else 'INF')

Submission status: Accepted

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


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

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

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq


graph = {}
inf = 1

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = float('inf')

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10 ** 12

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

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

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

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

Submission status: Accepted

Solution code:

from collections import namedtuple
from heapq import heappop, heappush


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


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

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

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


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

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

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

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

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

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


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

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

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


if __name__ == '__main__':
    run()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
import heapq as h

inf = sys.maxsize

# おまじない
class heapq:
    def __init__(self):
        self.q = []

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

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


V,e,r=(int (i)for i in input().split())
#print(v)
G=[[] for i in range(V)]#iごとに[]（式）を評価(実行)する。
for j in range(e):
    f,t,cost=(int (i)for i in input().split())
    G[f].append((t,cost))
dist=[inf]*100000
visited=[False]*100000
a=heapq()
a.push((0,r))
def end(visited):
    for i in visited:
        if i==False:
            return False
    return True
while(not a.is_empty()):
    (cur_dist,u)=a.pop()#uはid,cur_distはいまの道の長さ
    if not visited[u]:
        
        dist[u]=cur_dist
        #print(cur_dist,u)
        visited[u]=[True]
        for (v,cost) in G[u]:
            if not visited[v] and dist[u]+cost<dist[v]:
                a.push((dist[u]+cost,v))
#print(v)
for i in range(V):
    if dist[i]==inf:
        print('INF')
    else:
        print(dist[i])

Submission status: Runtime Error

Solution code:
import sys
import queue


class Dijkstra:
    class Edge:
        def __init__(self, end, cost):
            self.to = end
            self.cost = cost

    def __init__(self, node_size, inf):
        self._node = node_size
        self._graph = [[] for _ in range(self._node)]
        self.inf = inf
        self.dist = [self.inf for _ in range(self._node)]

    def add_edge(self, st, ed, cs):
        self._graph[st].append(self.Edge(ed, cs))

    def solve(self, start):
        que = queue.PriorityQueue()
        self.dist[start] = 0
        que.put((0, start))
        while que:
            cur_cost, cur_vertex = que.get()
            if self.dist[cur_vertex] < cur_cost:
                continue
            for e in self._graph[cur_vertex]:
                if self.dist[e.to] > cur_cost + e.cost:
                    self.dist[e.to] = cur_cost + e.cost
                    que.put((self.dist[e.to], e.to))


if __name__ == '__main__':
    V, E, r = map(int, sys.stdin.readline().split())
    dk = Dijkstra(V, 10 ** 10)
    for i in range(E):
        s, t, d = map(int, sys.stdin.readline().split())
        dk.add_edge(s, t, d)
    dk.solve(r)
    for value in dk.dist:
        if value == dk.inf:
            print("INF")
        else:
            print(value)

Submission status: Runtime Error

Solution code:
# AOJ GRL_1_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

INF = 100000000

def solve(v, e, dic):
    dp = []
    for i in range(0, v):
        dp += [[INF] * v ]
        for t, d in dic[i]:
            dp[i][t] = d
        dp[i][i] = 0
    for k in range(0, v):
        for i in range(0, v):
            for j in range(0, v):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
    return dp

dic = {}
dp = []
line = input()
v, e, r = list(map(int, line.split()))
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    if s not in dic:
        dic[s] = [[t, d]]
    else:
        dic[s] += [[t, d]]
dp = solve(v, e, dic)
for i in range(0, v):
    print(dp[r][i] if dp[r][i] != INF else "INF")

Submission status: Runtime Error

Solution code:
# AOJ GRL_1_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

INF = 100000000

def solve(v, e, dic):
    dp = []
    for i in range(0, v):
        dp += [[INF] * v ]
        for t, d in dic[i]:
            dp[i][t] = d
        dp[i][i] = 0
    for k in range(0, v):
        for i in range(0, v):
            for j in range(0, v):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
    return dp

dic = {}
dp = []
line = input()
v, e, r = list(map(int, list(line.split())))
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, list(line.split())))
    if s not in dic:
        dic[s] = [[t, d]]
    else:
        dic[s] += [[t, d]]
dp = solve(v, e, dic)
for i in range(0, v):
    print(dp[r][i] if dp[r][i] != INF else "INF")

Submission status: Runtime Error

Solution code:
# AOJ GRL_1_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

INF = 100000000

def solve(v, dic):
    dp = []
    for i in range(0, v):
        dp += [[INF] * v ]
        for t, d in dic[i]:
            dp[i][t] = d
        dp[i][i] = 0
    for k in range(0, v):
        for i in range(0, v):
            for j in range(0, v):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
    return dp

dic = {}
dp = []
line = input()
v, e, r = list(map(int, list(line.split())))
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, list(line.split())))
    if s not in dic:
        dic[s] = [[t, d]]
    else:
        dic[s] += [[t, d]]
dp = solve(v, dic)
for i in range(0, v):
    print(dp[r][i] if dp[r][i] != INF else "INF")

Submission status: Runtime Error

Solution code:
# AOJ GRL_1_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

import sys

INF = 100000000

def solve(v, dic):
    dp = []
    for i in range(0, v):
        dp += [[INF] * v ]
        for t, d in dic[i]:
            dp[i][t] = d
        dp[i][i] = 0
    for k in range(0, v):
        for i in range(0, v):
            for j in range(0, v):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
    return dp

dic = {}
dp = []
line = input()
v, e, r = list(map(int, list(line.split())))
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, list(line.split())))
    if s not in dic:
        dic[s] = [[t, d]]
    else:
        dic[s] += [[t, d]]
dp = solve(v, dic)
for i in range(0, v):
    print(dp[r][i] if dp[r][i] != INF else "INF")

Submission status: Runtime Error

Solution code:
# AOJ GRL_1_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

from heapq import heappush, heappop

INF = 100000000

def solve(r, t, v, dic):
    dp = []
    q = []
    dp = [INF] * v
    dp[r] = 0
    heappush(q, (0, r))
    while q:
        cost, vtx = heappop(q)
        if dp[vtx] < cost:
            continue
        if vtx not in dic:
            continue
        for vtx1, cost1 in dic[vtx]:
            if cost + cost1 < dp[vtx1]:
                dp[vtx1] = cost + cost1
                heappush(q, (cost + cost1, vtx1))
    return dp

dic = {}
dp = []
line = input()
v, e, r = list(map(int, line.split()))
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    if s not in dic:
        dic[s] = [[t, d]]
    else:
        dic[s] += [[t, d]]
dp = solve(r, t, v, dic)
for t in range(0, v):
    print(dp[t] if dp[t] != INF else "INF")

Submission status: Runtime Error

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

    @property
    def E(self):
        """ 辺数 
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges[(_from, _to)] = _cost
        self.v_set.add(_from)
        self.v_set.add(_to)
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)
            # キューに格納されている最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                if not (v,i) in self.edges: continue

                cost = self.edges[(v,i)]  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d


if __name__ == "__main__":
    djk = Dijkstra()
    V, E, s = list(map(int, input().split()))
    for i in range(E):
        _from, to, cost = list(map(int, input().split()))
        djk.add(_from, to, cost)

    d = djk.shortest_path(s)
    
    for cost in d:
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Submission status: Runtime Error

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

    @property
    def E(self):
        """ 辺数 
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges[(_from, _to)] = _cost
        self.v_set.add(_from)
        self.v_set.add(_to)
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)
            # キューに格納されている最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                if not (v,i) in self.edges: continue

                cost = self.edges[(v,i)]  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d


if __name__ == "__main__":
    djk = Dijkstra()
    V, E, s = list(map(int, input().split()))
    if E == 0:
        print(0)
    
    for i in range(E):
        _from, to, cost = list(map(int, input().split()))
        djk.add(_from, to, cost)

    d = djk.shortest_path(s)
    
    for cost in d:
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)