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: Wrong Answer

Solution code:

#Bellman-FordだとTLEになる(はず)
V,E,r = map(int, input().split())
edges = []
for _ in range(E):
    tmp = [int(x) for x in input().split()]
    edges.append(tmp)

d = [float('inf') for _ in range(V)]
d[r] = 0

for _ in range(V-1):
    count = 0
    for x in edges:
        if d[x[1]] > d[x[0]] + x[2]:
            count += 0
            d[x[1]] = d[x[0]] + x[2]
    if count == 0:
        break

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

Submission status: Wrong Answer

Solution code:
inf = 0xf0f0f0f0
def solve(G,start):
	cost = [inf]*V
	visited = [False]*V
	cost[start] = 0
	while 1:
		visited[start] = True
		next = -1
		min = inf
		for i in range(V):
			if visited[i]: continue
			if G[start][i]:
				d = cost[start] + G[start][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i	
		start = next
		if next == -1: break
	return cost

V,E,r = map(int,raw_input().split())
G = [[0]*V for i in range(V)]
for i in range(E):
	s,t,d = map(int,raw_input().split())
	G[s][t] = d
cost = solve(G,r)
for i in range(V):
	print cost[i] if cost[i] < inf else "INF"

Submission status: Wrong Answer

Solution code:
inf = 0xf0f0f0f0
def solve(G,start):
	cost = [inf]*V
	prev = [None]*V
	visited = [False]*V
	cost[start] = 0
	while 1:
		visited[start] = True
		next = -1
		min = inf
		for i in range(V):
			if visited[i]: continue
			if G[start][i]:
				d = cost[start] + G[start][i]
				if d < cost[i]:
					cost[i] = d
					prev[i] = start
			if min > cost[i]:
				min = cost[i]
				next = i	
		start = next
		if next == -1: break
	return prev

V,E,r = map(int,raw_input().split())
G = [[0]*V for i in range(V)]
GC = [[inf]*V for i in range(V)]
for i in range(E):
	s,t,d = map(int,raw_input().split())
	G[s][t] = 1
	GC[s][t] = d
	
prev = solve(G,r)
prev[r] = r
cost = [0]*V
for i in range(V):
	if prev[i] is None:
		cost[i] = inf
		continue
	j = i
	while 1:
		if j == prev[j]: break
		cost[i] += GC[prev[j]][j]
		j = prev[j]
for i in cost:
	print i if i < inf else "INF"

Submission status: Wrong Answer

Solution code:
inf = 0xf0f0f0f0
def solve(G,start):
	cost = [inf]*V
	visited = [False]*V
	cost[start] = 0
	while 1:
		visited[start] = True
		next = -1
		min = inf
		for i in range(V):
			if visited[i]: continue
			if G[start][i]:
				d = cost[start] + G[start][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i	
		start = next
		if next == -1: break
	return cost

V,E,r = map(int,raw_input().split())
G = [[0]*V for i in range(V)]
for i in range(E):
	s,t,d = map(int,raw_input().split())
	G[s][t] = d
	
cost = solve(G,r)
for i in cost: print i if i < inf else "INF"

Submission status: Wrong Answer

Solution code:
inf = 1e10
def solve(G,start):
	cost = [inf]*V
	visited = [False]*V
	cost[start] = 0
	while 1:
		visited[start] = True
		next = -1
		min = inf
		for i in range(V):
			if visited[i]: continue
			if G[start][i]:
				d = cost[start] + G[start][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i	
		start = next
		if next == -1: break
	return cost

V,E,r = map(int,raw_input().split())
G = [[0]*V for i in range(V)]
for i in range(E):
	s,t,d = map(int,raw_input().split())
	G[s][t] = d
	
cost = solve(G,r)
for i in cost: print i if i < inf else "INF"

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq as hp


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


class Dijkstra:
    def __init__(self, V):
        self._node = V
        self._graph = [[] for i in range(self._node)]
        self._inf = sys.maxsize
        self.dist = [self._inf for i in range(self._node)]

    def add_edge(self, st, ed, cost):
        self._graph[st].append(Edge(ed, cost))
    def solve(self, s):
        que = []
        self.dist[s] = 0
        hp.heappush(que, (0, s))
        while que:
            info = hp.heappop(que)
            cur_cost, cur_vertex = info
            if self.dist[cur_vertex] < cur_cost:
                continue
            for e in self._graph[cur_vertex]:
                if cur_cost + e.cost < self.dist[e.to]:
                    self.dist[e.to] = cur_cost + e.cost
                    hp.heappush(que, (self.dist[e.to], e.to))
                    hp.heapify(que)


if __name__ == '__main__':
    V, E, r = map(int, sys.stdin.readline().split())
    dk = Dijkstra(V)
    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 == sys.maxsize:
            sys.stdout.writelines("INF\n")
        else:
            sys.stdout.writelines("%d\n" % value)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq as hp

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


class Dijkstra:
    def __init__(self, V):
        self._node = V
        self._graph = [[] for i in range(self._node)]
        self._inf = sys.maxsize
        self.dist = [self._inf for i in range(self._node)]

    def add_edge(self, st, ed, cost):
        self._graph[st].append(Edge(ed, cost))
    def solve(self, s):
        que = []
        self.dist[s] = 0
        hp.heappush(que, (0, s))
        while que:
            info = hp.heappop(que)
            cur_cost, cur_vertex = info
            if self.dist[cur_vertex] < cur_cost:
                continue
            for e in self._graph[cur_vertex]:
                if cur_cost + e.cost < self.dist[e.to]:
                    self.dist[e.to] = cur_cost + e.cost
                    hp.heappush(que, (self.dist[e.to], e.to))
                    hp.heapify(que)


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

Submission status: Time Limit Exceeded

Solution code:
v,e,r = map(int,input().split())
d = [float('INF')]*v
d[r] = 0
edges=[]

for i in range(e):
  s,t,c = map(int,input().split())
  edges.append([s,t,c])

for i in range(v):
  for s,v,c in edges:
    if d[v] > d[s]+c:
      d[v] = d[s]+c

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

Submission status: Time Limit Exceeded

Solution code:
v,e,r = map(int,input().split())
d = [float('INF')]*v
d[r] = 0
edges=[[] for i in range(v)]
visited = [False]*v

for i in range(e):
  s,t,c = map(int,input().split())
  edges[s].append([t,c])

while not all (visited):
  dmin = float('INF')
  for i, (du,v) in enumerate(zip(d,visited)):
    if dmin > du and not v:
      dmin, u = du, i
  visited[u] = True
  for v,c in edges[u]:
    if d[v] > d[u]+ c:
      d[v] = d[u]+c

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

Submission status: Time Limit Exceeded

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 ]
        if i in dic:
            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: Time Limit Exceeded

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()
    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: Time Limit Exceeded

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()
    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: Time Limit Exceeded

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

        Args:
            V(int): 頂点数
                    - 頂点数が与えられたときは、すべての辺をINFで初期化する
        """
        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)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                
                cost = self.edges.get((v,i), float("inf"))  # 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()
    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: Time Limit Exceeded

Solution code:
import sys

inf = sys.maxsize

# 入力:graphと始点s
# 出力:始点sから各頂点tへの距離dist
def shortestPath(graph, s):
    n = len(graph)

    dist    = [inf for _ in range(n)]
    visited = [False for _ in range(n)]
    dist[s] = 0

    while True:
        idx, u  = -1, inf
        for i in range(n):
            if not visited[i] and dist[i] < u:
                idx = i
                u = dist[i]
        
        if u == inf: break
        
        visited[idx] = True

        for (next, w) in graph[idx]:
            newdist = w + dist[idx]
            if newdist < dist[next]:
                dist[next] = newdist
    return dist

def main():
    v, e, s = map(int, input().split())
    
    # 隣接リスト
    graph = [[] for _ in range(v)]
    
    for i in range(e):
        a, b, cost = map(int, input().split())
        graph[a].append((b, cost))
            
    c_dist = shortestPath(graph, s)
            
    for d in c_dist:
        if d == inf:
            print("INF")
        else:
            print(d)
main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
V,E,r = map(int,raw_input().split())
edges = [[] for i in range(V)]

for i in xrange(E):
	(a,b,w) = map(int,raw_input().split())
	edges[a].append({'to':b,'weight':w})

INF = 2000000000

distance = [INF] * V	# A??????????????¢
visited = [False] * V	# ??????????¨??????????????????????

distance[r] = 0
for i in range(V):
	min_v = -1
	for v in range(V):
		if not visited[v] and (min_v == -1 or distance[v] < distance[min_v]):
			min_v = v
	visited[min_v] = True
	for e in edges[min_v]:
		distance[e['to']] = min(distance[min_v] + e['weight'],distance[e['to']])

for d in distance:
	print 'INF' if d == INF else d

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
INF = 1000000

# ?¨??????\???????????\????????¢?????§????????????
# |V| |E|
# ai bi wi
V,E,r = map(int,raw_input().split())
edges = [[] for i in range(V)]	# ??£??\?????????

for i in xrange(E):
	a,b,w = map(int,raw_input().split())
	edges[a].append({'to':b,'weight':w})
	# edges[b].append({'to':a,'weight':w})

distance = [INF] * V
visited = [False] * V

distance[r] = 0
for i in range(V):
	min_v = -1
	for v in range(V):
		if not visited[v] and (min_v == -1 or distance[v] < distance[min_v]):
			min_v = v

	visited[min_v] = True
	for e in edges[min_v]:
		distance[e['to']] = min(distance[min_v] + e['weight'],distance[e['to']])

for d in distance:
	if d >= INF:
		print "INF"
	else:
		print d

Submission status: Time Limit Exceeded

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

    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 = deepcopy(E)
        self.dijkstra(start, INF)

    def dijkstra(self, start, INF):
        que = list()
        self.distance = [INF for _ in range(self.V)] # distance from
        self.prev = [-1 for _ in range(self.V)] # prev vertex of shortest path
        self.distance[start] = 0
        heappush(que, (0, start))

        while len(que) > 0:
            dist, v = heappop(que)
            dist = abs(dist)
            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))
                    self.prev[to] = v

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

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 dist in sp.distance:
    print(dist if dist != INF else 'INF')

Submission status: Time Limit Exceeded

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

    def __init__(self, V, E, start, INF=maxsize):
        """ 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 for _ in range(self.V)] # distance from
        self.prev = [-1 for _ in range(self.V)] # prev vertex of shortest path
        self.distance[start] = 0
        heappush(que, (0, start))

        while len(que) > 0:
            dist, v = heappop(que)
            dist = abs(dist)
            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))
                    self.prev[to] = v

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

V, E, r = map(int, input().split())
INF = maxsize
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 dist in sp.distance:
    print(dist if dist != INF else 'INF')

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
from sys import maxsize

class Dijkstra:
    """Dijkstra's algorithm : find the shortest path from a vertex
    """

    def __init__(self, V, E, start, INF=maxsize):
        """ 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 for _ in range(self.V)] # distance from
        self.distance[start] = 0
        heappush(que, (0, start))

        while len(que) > 0:
            dist, v = heappop(que)
            dist = abs(dist)
            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 = maxsize
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 dist in sp.distance:
    print(dist if dist != INF else 'INF')

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
from sys import maxsize

def dijkstra(start, INF):
    que = list()
    distance = [INF for _ in range(V)] # distance from
    distance[start] = 0
    heappush(que, (0, start))
    
    while len(que) > 0:
        dist, v = heappop(que)
        dist = abs(dist)
        if distance[v] < dist: continue
        for to, cost in edge[v]:
            if distance[v] + cost < distance[to]:
                distance[to] = distance[v] + cost
                heappush(que, (-distance[to], to))
    for d in distance:
        print(d if d != INF else 'INF')

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

Submission status: Time Limit Exceeded

Solution code:
INF = 1000000000
class Edge:
	def __init__(self, to, cost):
		self.to = to
		self.cost = cost


def dijkstra(graph, start):
	V = len(graph)
	d = [INF for _ in xrange(V)]
	d[start] = 0

	done = [False for _ in xrange(V)]
	while True:
		mini = INF
		min_i = -1
		for i, node in enumerate(graph):
			if done[i] == False:
				if d[i] < mini:
					min_i = i
					mini = d[i]			
		if min_i == -1:
			return d
			
		done[min_i] = True
			
		node = graph[min_i]
		for edge in node:
			if d[min_i] + edge.cost < d[edge.to]:
				d[edge.to] = d[min_i] + edge.cost

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

	graph = [[] for _ in xrange(V)]
	for i in xrange(E):
		_s, _t, _c = map(int, raw_input().split())
		graph[_s].append(Edge(_t, _c))


	distance = dijkstra(graph, r)
	for d in distance:
		if d == INF:
			print "INF"
		else:
			print d




if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

class UnionFindSet:
	def __init__(self, nodes):
		self.fa = {}
		for n in nodes:
			self.fa[n] = n

	def find(self, x):
		if self.fa[x] == x:
			return x
		else:
			self.fa[x] = self.find(self.fa[x])
			return self.fa[x]

	def union(self, x, y):
		fx = self.find(x)
		fy = self.find(y)
		if fx == fy:
			return fx
		else:
			self.fa[fx] = fy
			return fy


"""
graph is a hash
graph["nodes"] is a list of all nodes in the graph
graph["edges"] is a list of all edges in the graph in (x, y, w) form
  - x is the first nodes
  - y is the second nodes
  - w is the weight of the edges
graph["relation"] is the graph relation of the graph
"""

def kruscal(graph):
	"kruscal minimum spanning tree algorithm"
	ufset = UnionFindSet(graph["nodes"])

	ret = 0

	for (x, y, w) in sorted(graph["edges"], key = lambda x: x[-1]):
		fx = ufset.find(x)
		fy = ufset.find(y)
		if fx != fy:
			ret += w
			ufset.union(fx, fy)
		else:
			pass
	return ret


def dijkstra(graph, root):
	dis, vis = {}, {}
	for n in graph["nodes"]:
		dis[n] = 10 ** 9
		vis[n] = False

	heap = []
	dis[root] = 0
	heappush(heap, (0, root))

	while heap:
		_, n = heappop(heap)
		vis[n] = True
		for (y, w) in graph["adj"][n]:
			if not vis[y]:
				dis[y] = min(dis[y], dis[n] + w)
				heappush(heap, (dis[y], y))

	return dis

if __name__ == '__main__':
	V, E, root = map(int, raw_input().strip().split())
	graph = {}
	graph["nodes"] = [i for i in range(V)]
	graph["edges"] = []
	graph["adj"] = defaultdict(list)
	for _ in range(E):
		x, y, w = map(int, raw_input().strip().split())
		graph["edges"].append((x, y, w))
		graph["adj"][x].append((y, w))

	dis = dijkstra(graph, root)

	for n in graph["nodes"]:
		print dis[n] if dis[n] < 10 ** 9 else "INF"

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# ref. http://www.deqnotes.net/acmicpc/dijkstra/

from heapq import heappush, heappop

class Node:
    def __init__(self, name):
        self.name = name
        self.edges_to = []
        self.edges_cost = []
        self.done = False
        self.cost = -1

if __name__ == "__main__":
    # set a graph
    V, E, r = map(int, raw_input().split())
    nodes = []
    for i in xrange(V):         # V??????Node????????????
        nodes.append(Node(i)) 
    
    for i in xrange(E):
        s, t, d = map(int, raw_input().split())
        nodes[s].edges_to.append(t)
        nodes[s].edges_cost.append(d)
    
    # dijkstra by priority queue(heapq)
    hq = []
    nodes[r].cost = 0           #?§????r???????????????0
    nodes[r].done = True  
    heappush(hq, nodes[r])
    
    while len(hq)!= 0:          # r????????????????????????????????????????????????????±??????????
        done_node = heappop(hq)
        done_node.done = True
        for to, cost in zip(done_node.edges_to, done_node.edges_cost):
            new_cost = done_node.cost + cost
            if nodes[to].cost < 0 or new_cost < nodes[to].cost:
                nodes[to].cost = new_cost
                if nodes[to] not in hq:
                    heappush(hq, nodes[to])
            
    for item in nodes:
        if item.cost == -1:
            print "INF"
        else:
            print item.cost