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: 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)
        return
    
    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, V=None):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点数
                    - 頂点数が与えられたときは、すべての辺をINFで初期化する
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

        if V is not None:
            for u in range(V):
                for v in range(V):
                    self.edges[(u,v)] = float("INF")

    @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__":
    V, E, s = list(map(int, input().split()))
    djk = Dijkstra(V)
    """
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
    """
    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 BellmanFord():
    """ ベルマンフォード法
    重み付き有向グラフにおける単一始点最短路アルゴリズム
    
    * 使用条件
        - DAG（有向グラフで閉路を持たない）であること
        - 負のコストがあってもOK
    
    * 負の閉路がある場合、最短路は求まらないが、負の閉路の検出はできる
    
    * 計算量はO(V*E)
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _from, _to, _cost):
            self.from_ = _from
            self.to = _to
            self.cost = _cost
        
    def __init__(self):
        self.edges = []  # 辺
        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.append(self.Edge(_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までの最短路
        """
        d = [float("inf")] * self.V
        d[s] = 0
    
        while True:
            do_update = False
            for i in range(self.E):
                e = self.edges[i]
                if d[e.from_] != float("inf") and d[e.to] > d[e.from_]+e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    do_update = True
            
            if not do_update: break
        
        return d
    
    def exist_negative_loop(self):
        """ 負の閉路が存在するか否か
        Returns:
            (bool): 負の閉路が存在する(True)/しない(False)
        """
        d = [0] * self.V
        for i in range(self.V):
            for j in range(self.E):
                e = self.edges[j]
                if d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    # n回目にも更新があるなら負の閉路が存在する
                    if i == self.V-1: return True
        return False
    
if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    bf = BellmanFord()
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            bf.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            bf.add(_from, to, cost)

    d = bf.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Submission status: Runtime Error

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

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

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

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self, V=None):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点数
                    - 頂点数が与えられたときは、すべての辺をINFで初期化する
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

        if V is not None:
            for u in range(V):
                for v in range(V):
                    self.edges[(u,v)] = float("INF")

    @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)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                """
                try:
                    self.edges[(v,i)]
                except KeyError:
                    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__":
    V, E, s = list(map(int, input().split()))
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in djk.v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Submission status: Runtime Error

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

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

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

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := uに隣接してるi番目の頂点
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    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)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                cost = self.G[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__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Submission status: Runtime Error

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

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

e = defaultdict(list)
for i in range(E):
    s, t, length = map(int, input())
    e[s].append((length, t))

distance = [float('inf')] * v          # 各頂点への距離の初期値
distance[r] = 0                        # 始点への距離は 0

# ダイクストラ
heap = [(distance[r], r)]
while heap:
    du, u = heappop(heap)
    for length, v in e[u]:
        if distance[v] > e[u] + length:
            distance[v] = e[u] + length
            heappush(heap, (distance[v], v))

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

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
V, E, r = map(int, raw_input().split())
g = [[] for i in xrange(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    g[s].append((t, d))

INF = 10**10
dist = [INF]*V
que = [(0,r)]
dist[r] = 0
while que:
    c, v = heappop(que)
    if dist[v] < c:
        continue
    for t, cost in g[v]:
        if dist[v] + cost < dist[t]:
            dist[t] = dist[v] + cost
            heappush(que, (t, dist[t]))
for i in xrange(V):
    print dist[i] if dist[i]<INF else "INF"

Submission status: Runtime Error

Solution code:
import heapq


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

    def __lt__(self, e):
        return self.weight > e.weight


class Graph:
    def __init__(self, V):
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, src, dst, weight):
        self.E[src].append(Edge(dst, weight))


class ShortestPath:
    """Dijkstra's algorithm : find the shortest path from a vertex
       Complexity: O(E + log(V))
       used in GRL1A(AOJ)
    """

    def __init__(self, G, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (all edge in E must be 0 or positive)
            start: start vertex
            INF: Infinity distance
        """
        self.G, self.INF = G, INF

    class Node:
        def __init__(self, v, cost):
            self.v, self.cost = v, cost

        def __lt__(self, n):
            return self.cost > n.cost

    def dijkstra(self, start, goal=None):
        que = list()
        self.dist = [self.INF] * self.G.V  # distance from start
        self.dist[start] = 0
        heapq.heappush(que, self.Node(start, 0))

        while len(que) > 0:
            n = heapq.heappop(que)
            if self.dist[n.v] < n.cost:
                continue
            if goal is not None and n.v == goal:
                return
            for e in self.G.E[n.v]:
                if self.dist[n.v] + e.weight < self.dist[e.dst]:
                    self.dist[e.dst] = self.dist[n.v] + e.weight
                    heapq.heappush(que, self.Node(e.dst, self.dist[e.dst]))
                    self.prev[e.dst] = n.v

V, E, start = map(int, input().split())
G = Graph(V)
for _ in range(E):
    s, t, d = map(int, input().split())
    G.add_edge(s, t, d)
INF = 10**9
sp = ShortestPath(G, INF)
sp.dijkstra(start)
for i in range(G.V):
    print("INF" if sp.dist[i] == INF else sp.dist[i])

Submission status: Runtime Error

Solution code:
import heapq


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

    def __lt__(self, e):
        return self.weight > e.weight


class Graph:
    def __init__(self, V):
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, src, dst, weight):
        self.E[src].append(Edge(dst, weight))


class ShortestPath:
    """Dijkstra's algorithm : find the shortest path from a vertex
       Complexity: O(E + log(V))
       used in GRL1A(AOJ)
    """

    def __init__(self, G, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (all edge in E must be 0 or positive)
            start: start vertex
            INF: Infinity distance
        """
        self.G, self.INF = G, INF

    class Node:
        def __init__(self, v, cost):
            self.v, self.cost = v, cost

        def __lt__(self, n):
            return self.cost < n.cost

    def dijkstra(self, start, goal=None):
        que = list()
        self.dist = [self.INF] * self.G.V  # distance from start
        self.prev = [-1] * self.G.V  # prev vertex of shortest path
        self.dist[start] = 0
        heapq.heappush(que, self.Node(start, 0))

        while len(que) > 0:
            cost, v = heapq.heappop(que)
            if self.dist[v] < cost:
                continue
            if goal is not None and v == goal:
                return
            for e in self.E[v]:
                if self.dist[v] + e.weight < self.dist[e.dst]:
                    self.dist[e.dst] = self.dist[v] + e.weight
                    heapq.heappush(que, self.Node(e.dst, self.dist[e.dst]))
                    self.prev[e.dst] = v

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

V, E, start = map(int, input().split())
G = Graph(V)
for _ in range(E):
    s, t, d = map(int, input().split())
    G.add_edge(s, t, d)
INF = 10**9
sp = ShortestPath(G, INF)
sp.dijkstra(start)
for i in range(G.V):
    print("INF" if sp.dist[i] == INF else sp.dist[i])

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappush, heappop
from collections import Counter, defaultdict, deque, OrderedDict
from sys import setrecursionlimit as setreclim
from sys import maxsize
from bisect import bisect_left, bisect, insort_left, insort
from math import ceil, log, factorial, hypot, pi
from fractions import gcd
from copy import deepcopy
from functools import reduce
from operator import mul
from itertools import product, permutations, combinations, accumulate, cycle
from string import ascii_uppercase, ascii_lowercase, ascii_letters, digits, hexdigits, octdigits
????
prod = lambda l: reduce(mul, l)
prodmod = lambda l, mod: reduce(lambda x, y: mul(x,y)%mod, l)
????
class Dijkstra:
????????"""Dijkstra's algorithm : find the shortest path from a vertex
??????????????used in GRL1A(AOJ)
????????"""
????
????????def __init__(self, V, E, start, INF=10**9):
????????????????""" V: the number of vertexes
????????????????????????E: adjacency list
????????????????????????start: start vertex
????????????????????????INF: Infinity distance
????????????????"""
????????????????self.V = V
????????????????self.E = E
????????????????self.dijkstra(start, INF)
????
????????def dijkstra(self, start, INF):
????????????????que = list()
????????????????self.distance = [INF] * self.V # distance from start
????????????????self.distance[start] = 0
????????????????heappush(que, (0, start))
????
????????????????while len(que) > 0:
????????????????????????dist, v = heappop(que)
????????????????????????if self.distance[v] < dist: continue
????????????????????????for to, cost in self.E[v]:
????????????????????????????????if self.distance[v] + cost < self.distance[to]:
????????????????????????????????????????self.distance[to] = self.distance[v] + cost
????????????????????????????????????????heappush(que, (self.distance[to], to))
????
V, E, r = map(int, input().split())
INF = 10**10
edge = [[] for _ in range(V)]
for i in range(E):
????????s, t, cost = map(int, input().split())
????????edge[s].append((t, cost))
sp = Dijkstra(V, edge, r, INF)
for d in sp.distance:
????????print(d if d != INF else 'INF')

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3


from collections import defaultdict

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    visited = []
    #unseen = [R]
    d = {}
    d[0] = 0
    q = [R]
    while q != []:
        u = q.pop(0)
        if u not in visited:
            for v in G[u]:
                if v[0] not in visited:
                    d[v[0]] = d[u] + v[1]
                    q.append(v[0])
            visited.append(u)

    for k in d.keys():
        print(d[k])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        #u = heappop(q)
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                #heappush(q, v[0])
                q.append(v[0])


    for k in d.keys():
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
#from collections import defaultdict

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]

    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])

    for k in d.keys():
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3

'''
time score 7.88 for list
time score 03.17 for deque
time score 03.22 for defaultdict(dict)

''' 

from collections import defaultdict
from collections import deque
#import time

def main():
    # Read stdin
    start = time.clock()
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    # Adjacency list
    G = defaultdict(list)
    for i in range(E):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t, w))
    # initialized
    d = {}
    INF = float('inf')
    # INF = 10001
    nodes_list = range(V)
    for i in nodes_list:
        d[i] = INF
    d[R] = 0
    # deque is better than list aka double link list O(1) for pop head and append
    q = deque([R])
    while q:
        # u = heappop(q)
        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                # heappush(q, v[0])
                q.append(v[0])
    for k in nodes_list:
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])
    #end = time.clock() - start
    #print('Computation time : {}'.format(end))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq

with open("input.txt","r") as f:
    vertice,edge,source = map(int,input().split(" "))
    link = [[] for n in range(vertice)]
    weight = defaultdict(dict)
    for e in range(edge):
        i,j,w = map(int,input().split(" "))
        link[i].append(j)
        weight[i].update({j:w})
    #print(weight,link)
    for v in range(vertice):
        goal = v
        queue = []
        heapq.heappush(queue,[0,source])
        went = set()

        while queue != []:
            #print(queue)
            now_cost,here = heapq.heappop(queue)
            #print(now_cost,here,queue)
            if here == goal:
                print(now_cost)
                break

            can_go = link[here]
            not_went = set(can_go) - went
            #print(v,here,now_cost,not_went,queue)
            for nw in not_went:
                next_cost = now_cost + weight[here][nw]
                heapq.heappush(queue,(next_cost,nw))
            went = went | {here}
            queue.sort(key=lambda x:x[1],reverse=True)
        else:
            print("INF")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().split(" "))
    link[i] = link.get(i,set()) | {j}
    weight[i].update({j:w})
#print(weight,link)
for v in range(vertice):
    goal = v
    queue = []
    heapq.heappush(queue,(0,source))
    heapq.heapify(queue)
    went = set()

    while queue != []:
        #print(queue)
        now_cost,here = heapq.heappop(queue)
        #print(now_cost,here,queue)
        if here == goal:
            print(now_cost)
            break

        can_go = link[here]
        not_went = can_go - went
        #print(v,here,now_cost,not_went,queue)
        for nw in not_went:
            next_cost = now_cost + weight[here][nw]
            heapq.heappush(queue,(next_cost,nw))
        went = went | {here}
    else:
        print("INF")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq

with open("input.txt","r") as f:
    vertice,edge,source = map(int,f.readline().split(" "))
    link = defaultdict(dict)
    weight = defaultdict(dict)
    for e in range(edge):
        i,j,w = map(int,f.readline().split(" "))
        link[i] = link.get(i,set()) | {j}
        weight[i].update({j:w})
    #print(weight,link)
    for v in range(vertice):
        goal = v
        queue = []
        heapq.heappush(queue,(0,source))
        heapq.heapify(queue)
        went = set()

        while queue != []:
            #print(queue)
            now_cost,here = heapq.heappop(queue)
            #print(now_cost,here,queue)
            if here == goal:
                print(now_cost)
                break

            can_go = link[here]
            not_went = set(can_go) - went
            #print(v,here,now_cost,not_went,queue)
            for nw in not_went:
                next_cost = now_cost + weight[here][nw]
                heapq.heappush(queue,(next_cost,nw))
            went = went | {here}
        else:
            print("INF")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
answer = [-1] * vertice
for e in range(edge):
    i,j,w = map(int,input().split(" "))
    link[i] = link.get(i,set()) | {j}
    weight[i].update({j:w})
goal = v
queue = []
heapq.heappush(queue,(0,source))
heapq.heapify(queue)
while queue:
    #print(queue)
    now_cost,here = heapq.heappop(queue)
    #print(now_cost,here,queue)
    if answer[here] > -1:
        continue
    answer[here] = now_cost

    #print(v,here,now_cost,not_went,queue)
    for nw in link[here]:
        if answer[nw] == -1:
            heapq.heappush(queue,(now_cost + weight[here][nw],nw))

for a in answer:
    print(a if a != -1 else "INF")

Submission status: Runtime Error

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


def sp(G,R,V):
    d = {}
    q = [(0, R)]
    d[R] = 0
    heapify(q)
    while q:
        (cost, v) = heappop(q)
        for (next, c) in G[v].items():
            if v not in d:
                d[v] = c
            elif d[next] > d[v] + c:
                d[next] = d[v] + c
                heappush(q, (d[next], next))
    return d



V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict(dict)
for case in range(E):
    s, t, w = [int(x) for x in stdin
    .readline().split()]
    G[s][t] = w
d = sp(G, R, V)
for k in range(V):
    if k not in d:
        print("INF")
    else:
        print(d[k])

Submission status: Runtime Error

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

def sp(G,R,V):
    d = {}
    q = [(0, R)]
    d[R] = 0
    heapify(q)
    while q:
        (cost, v) = heappop(q)
        for (next, c) in G[v].items():
            if v not in d:
                d[v] = c
            elif d[next] > d[v] + c:
                d[next] = d[v] + c
                heappush(q, (d[next], next))
    return d


V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict(dict)
for case in range(E):
    s, t, w = [int(x) for x in stdin
    .readline().split()]
    G[s][t] = w
d = sp(G, R, V)
for k in range(V):
    if k not in d:
        print("INF")
    else:
        print(d[k])