Problem:


Single Source Shortest Path

  For a given weighted graph G(V, E) and a source r, find the source shortest path to each vertex from the source (SSSP: Single Source Shortest Path).

Input

An edge-weighted graph G (V, E) and the source r.

|V| |E| r
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1

|V| is the number of vertices and |E| is the number of edges in G. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the source of the graph.

si and ti  represent source and target vertices of i-th edge (directed) and di represents the cost of the i-th edge.

Output

Print the costs of SSSP in the following format.

c0
c1
:
c|V|-1

The output consists of |V| lines. Print the cost of the shortest path from the source r to each vertex 0, 1, ... |V|-1 in order. If there is no path from the source to a vertex, print INF. 

Constraints

 1 ≤ |V| ≤ 100000

0 ≤ di ≤ 10000

 0 ≤ |E| ≤ 500000

 There are no parallel edges

 There are no self-loops

Sample Input 1

4 5 0
0 1 1
0 2 4
1 2 2
2 3 1
1 3 5

Sample Output 1

0
1
3
4

Sample Input 2

4 6 1
0 1 1
0 2 4
2 0 1
1 2 2
3 1 1
3 2 5

Sample Output 2

3
0
2
INF



Sample input:
4 5 0
0 1 1
0 2 4
1 2 2
2 3 1
1 3 5


Sample output:
0
1
3
4

Submission status: Accepted

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

# 入力:graphと始点s
# 出力:始点sから各頂点tへの距離dist
def shortestPath0(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 shortestPath1(graph, s):
    n = len(graph)

    dist    = [inf for _ in range(n)]
    visited = [False for _ in range(n)]
    
    q = heapq()
    q.push((0, s))

    while not q.is_empty():
        (cur_dist, v) = q.pop()

        if visited[v] or dist[v] <= cur_dist:
            continue

        dist[v] = cur_dist
        visited[v] = True

        for next, w in graph[v]:
            if not visited[next] and dist[v] + w < dist[next]:
                q.push((dist[v] + w, next))

    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 = shortestPath1(graph, s)
            
    for d in c_dist:
        if d == inf:
            print("INF")
        else:
            print(d)
main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop


def dijkstra(Graph, s):
    dis, vis, hq = {}, {}, []
    
    for node in Graph:
        dis[node], vis[node] = sys.maxint, False
        
    dis[s] = 0
    heappush(hq, (0, start))
    
    while hq:
        (d, node) = heappop(hq)
        vis[node] = True
        
        for n, weight in Graph[node].items():
            if d + weight < dis[n]:
                dis[n] = d + weight
                heappush(hq, (dis[n], n))
    return dis
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    V, E, start = line.split()
    V, E, start = int(V), int(E), int(start)
    G = {}
    for i in range(V):
        G[i] = {}
    
    for i in range(E):
        line = sys.stdin.readline()
        s, e, w = line.split()
        s, e, w = int(s), int(e), int(w)
        G[s][e] = w
    
    dis = dijkstra(G, start)
    for i in range(V):
        if dis[i] == sys.maxint:
            sys.stdout.write('INF\n')
        else:
            sys.stdout.write(str(dis[i]) + '\n')

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict, deque
import math

readline = stdin.readline


v, e, r = map(int, readline().split())

g = defaultdict(list)
for i in range(e):
    s, t, length = map(int, readline().split())
    g[s].append((length, t))
d = [float('inf')] * v
d[r] = 0
que = deque([(d[r], r)])
while que:
    du, u = que.popleft()
    for length, v in g[u]:
        if d[v] > du + length:
            d[v] = du + length
            que.append((d[v], v))
for di in d:
    print('INF' if math.isinf(di) else di)

Submission status: Accepted

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

readline = stdin.readline

v, e, r = map(int, readline().split())

g = defaultdict(list)
for i in range(e):
    s, t, length = map(int, readline().split())
    g[s].append((length, t))
d = [float('inf')] * v
d[r] = 0
heap = [(d[r], r)]
while heap:
    du, u = heappop(heap)
    for length, v in g[u]:
        if d[v] > du + length:
            d[v] = du + length
            heappush(heap,(d[v], v))
for di in d:
    print('INF' if math.isinf(di) else di)

Submission status: Accepted

Solution code:
import Queue

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

pq = Queue.PriorityQueue()
pq.put((0,r))

dist = [INF] * V
visited = [False] * V
dist[r] = 0
while not pq.empty():
	d,v = pq.get()
	visited[v] = True
	for e in edges[v]:
		if visited[e['to']] or dist[e['to']] < d+e['weight']: continue
		dist[e['to']] = d + e['weight']
		pq.put((d+e['weight'],e['to']))

for i in dist:
	print 'INF' if i == INF else i

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import Queue
INF = 10000000000000000

# ?¨??????\???????????\????????¢?????§????????????
# |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
pq = Queue.PriorityQueue()
pq.put((0,r))
while not pq.empty():
	d,v = pq.get()
	visited[v] = True
	for e in edges[v]:
		if visited[e['to']] or distance[v]+e['weight'] > distance[e['to']]: continue
		distance[e['to']] = distance[v] + e['weight']
		pq.put((d+e['weight'],e['to']))

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

# 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: Accepted

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.prev = [-1] * self.V # prev vertex of shortest path
        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))
                    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 d in sp.distance:
    print(d if d != INF else 'INF')

Submission status: Accepted

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.prev = [-1] * self.V # prev vertex of shortest path
        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))
                    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 d in sp.distance:
    print(d if d != INF else 'INF')

Submission status: Accepted

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.prev = [-1] * self.V # prev vertex of shortest path
        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))
                    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)
print(*[dist if dist != INF else 'INF' for dist in sp.distance], sep='\n')

Submission status: Accepted

Solution code:
import heapq
from collections import namedtuple

edge = namedtuple("edge","to cost")

def dijkstra(G, s):
    que = [[0, s]]
    V = len(G)
    d = [float("inf")] * V
    d[s] = 0
    while que:
        c, v = heapq.heappop(que)
        if d[v] > c: continue
        for e in G[v]:
            if d[e.to] > d[v] + e.cost:
                d[e.to] = d[v] + e.cost
                heapq.heappush(que, [d[e.to], e.to])

    return d

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(edge(t, d))

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from collections import defaultdict
from heapq import heappop, heappush
from math import isinf

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

e = defaultdict(list)
for i in range(E):
    s, t, length = map(int, input().split())
    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] > distance[u] + length:
            distance[v] = distance[u] + length
            heappush(heap, (distance[v], v))

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

Submission status: Accepted

Solution code:
import heapq

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

	pq = []
	heapq.heappush(pq, (d[start], start))

	while len(pq) != 0:
		done = heapq.heappop(pq)
		node = graph[done[1]]
		for edge in node:
			if done[0] + edge.cost < d[edge.to]:
				d[edge.to] = done[0]+ edge.cost
				heapq.heappush(pq, (d[edge.to], edge.to))

	return d

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: Accepted

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

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] and dis[n] + w < dis[y]:
				dis[y] = dis[n] + w
				heappush(heap, (dis[y], y))

	return dis

if __name__ == '__main__':
	V, E, root = map(int, stdin.readline().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, stdin.readline().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: Accepted

Solution code:
import heapq


class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        num = len(adj)
        dist = [float('inf') for i in range(num)]
        prev = [float('inf') for i in range(num)]

        dist[start] = 0
        q = []
        heapq.heappush(q, (0, start))
        
        while len(q) != 0:
            prov_const, src = heapq.heappop(q)

            if dist[src] < prov_const:
                continue

            for i in range(len(adj[src])):
                dest, cost = adj[src][i][0], adj[src][i][1]
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(q, (dist[dest], dest))
                    prev[dest] = src

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

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

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

        return list(reversed(path))

if __name__ == '__main__':
    p_inf = float('inf')
    l = map(int, raw_input().split())
    V, E, r = l[0], l[1], l[2]
    
    adj = [[] for i in range(V)]
    for i in range(E):
        l = map(int, raw_input().split())
        s, t, d = l[0], l[1], l[2]
        adj[s].append((t, d))

    d = Dijkstra()
    result = d.dijkstra(adj, r)
    for i in result:
        if i == p_inf:
            print 'INF'
        else:
            print i

Submission status: Accepted

Solution code:
from Queue import PriorityQueue
INF = 1<<31
v, e, r = map(int, raw_input().split())
edge = [[] for i in range(v)]
for i in xrange(e):
    a, b, w = map(int, raw_input().split())
    edge[a].append((b,w))
q = PriorityQueue()
q.put((0,r))
dist = [INF]*v
visited = [False]*v
dist[r] = 0
while not q.empty():
    d, V = q.get()
    visited[V] = True
    for t, w in edge[V]:
        if visited[t] or dist[t] < d + w: continue
        dist[t] = d + w
        q.put((d + w, t))
for i in dist:
    print "INF" if i == INF else i

Submission status: Accepted

Solution code:
import heapq
V, E, root = map(int, input().split())
visited = [False] * V
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
    s, t, d = map(int, input().split())
    nodes[s].append(t)
    cost[s].append(d)
dist = [float('inf')] * V
dist[root] = 0

h = [(0, root)]
while h:
    c, v = heapq.heappop(h)
    if visited[v]:
        continue
    visited[v] = True
    for i in range(len(nodes[v])):
        t = nodes[v][i]
        if dist[t] > c + cost[v][i]:
            dist[t] = c + cost[v][i]
            heapq.heappush(h, (c + cost[v][i], t))

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

Submission status: Accepted

Solution code:
import heapq
V, E, root = map(int, input().split())
visited = [False] * V
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
    s, t, d = map(int, input().split())
    nodes[s].append(t)
    cost[s].append(d)

dist = [float('inf')] * V
dist[root] = 0

h = [(0, root)]
while h:
    c, v = heapq.heappop(h)
    if visited[v]:
        continue
    visited[v] = True
    for i in range(len(nodes[v])):
        t = nodes[v][i]
        if dist[t] > c + cost[v][i]:
            dist[t] = c + cost[v][i]
        if not visited[t]:
            visited[v] = True
            heapq.heappush(h, (c + cost[v][i], t))

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

Submission status: Accepted

Solution code:
import heapq
V, E, root = map(int, input().split())
visited = [False] * V
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
    s, t, d = map(int, input().split())
    nodes[s].append(t)
    cost[s].append(d)

dist = [float('inf')] * V
dist[root] = 0

h = [(0, root)]
while h:
    c, v = heapq.heappop(h)
    if visited[v]:
        continue
    visited[v] = True
    for i in range(len(nodes[v])):
        t = nodes[v][i]
        nc = c + cost[v][i]
        if dist[t] > nc:
            dist[t] = nc
            heapq.heappush(h, (nc, t))

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

Submission status: Accepted

Solution code:
import heapq
import collections


class Graph:

    def __init__(self, size):
        self.size = size
        self.graph = [[] for i in range(size)]

    def add_edge(self, source, target, cost):
        self.graph[source].append(self.Edge(target, cost))

    def add_bidirectional_edge(self, source, target, cost):
        self.add_edge(source, target, cost)
        self.add_edge(target, source, cost)

    def min_dist_dijkstra(self, s):
        dist = [float('inf')] * self.size
        dist[s] = 0
        q = [(0, s)]
        while q:
            node = self.Node(*heapq.heappop(q))
            v = node.id
            if dist[v] < node.dist:
                continue
            for e in self.graph[v]:
                if dist[e.target] > dist[v] + e.cost:
                    dist[e.target] = dist[v] + e.cost
                    heapq.heappush(q, (dist[e.target], e.target))
        return dist

    def min_path_dijkstra(self, s, t):
        dist = [float('inf')] * self.size
        prev = [-1] * self.size
        dist[s] = 0
        q = [(0, s)]
        while q:
            node = self.Node(*heapq.heappop(q))
            v = node.id
            if dist[v] < node.dist:
                continue
            for e in self.graph[v]:
                if dist[e.target] > dist[v] + e.cost:
                    dist[e.target] = dist[v] + e.cost
                    heapq.heappush(q, (dist[e.target], e.target))
                    prev[e.target] = v
            if v == t:
                break

        path = [t]
        while path[-1] > -1:
            path.append(prev[path[-1]])
        return path[1:]

    def min_dist_queue(self, s):
        dist = [float('inf')] * self.size
        dist[s] = 0
        q = collections.deque()
        q.append(s)
        while q:
            v = q.popleft()
            for e in self.graph[v]:
                if dist[e.target] > dist[v] + e.cost:
                    dist[e.target] = dist[v] + e.cost
                    if e.cost == 0:
                        q.appendleft(e.target)
                    else:
                        q.append(e.target)
        return dist

    def __str__(self):
        res = ''
        for i in range(self.size):
            res += str(i)
            for e in self.graph[i]:
                res += ' ' + str(e.target)
            res += '\n'
        return res

    class Edge:

        def __init__(self, target, cost):
            self.target = target
            self.cost = cost

    class Node:

        def __init__(self, dist, i):
            self.dist = dist
            self.id = i

        def __cmp__(self, other):
            if self.dist < other.dist:
                return -1
            elif self.dist == other.dist:
                return 0
            else:
                return 1

V, E, root = map(int, input().split())
g=Graph(V)
for i in range(E):
    s, t, d = map(int, input().split())
    g.add_edge(s,t,d)
dist = g.min_dist_dijkstra(root)
for i in range(V):
    if dist[i] == float('inf'):
        print('INF')
    else:
        print(dist[i])

Submission status: Accepted

Solution code:
import heapq

nv, ne, r = map(int, input().split())

edges = [set() for _ in range(nv)]
costs = [-1] * nv

while ne:
    s, t, d = map(int, input().split())
    edges[s].add((d, t))
    ne -= 1

queue = list(edges[r])
heapq.heapify(queue)
costs[r] = 0

while queue:
    total_cost, idx = heapq.heappop(queue)
    if costs[idx] > -1:
        continue
    costs[idx] = total_cost
    for cost, idx2 in edges[idx]:
        if costs[idx2] == -1:
            heapq.heappush(queue, (total_cost + cost, idx2))

for cost in costs:
    print(cost if cost > -1 else 'INF')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import collections
import heapq


G_INF = 2 ** 31


class Dijkstra(object):

    def __init__(self, number_of_vertices, adjacency_list, costs, start):
        self.max_v = number_of_vertices
        self.adj = adjacency_list
        self.costs = costs
        self.start = start
        self.dist = None

    def initialize_dist(self):
        self.dist = collections.defaultdict(lambda: G_INF)
        self.dist[self.start] = 0

    def single_source_shortest_path(self):
        self.initialize_dist()
        pq = [(self.dist[v], v) for v in range(self.max_v)]
        heapq.heapify(pq)
        while pq:
            (_, v) = heapq.heappop(pq)
            for u in self.adj[v]:
                new_length = self.dist[v] + self.costs[(v, u)]
                if new_length < self.dist[u]:
                    self.dist[u] = new_length
                    heapq.heappush(pq, (new_length, u))
        return self.dist


def main():
    max_v, max_e, start = map(int, input().split())
    adjacency_list = collections.defaultdict(lambda: array.array("L"))
    costs = collections.defaultdict(lambda: G_INF)
    for _ in range(max_e):
        s, t, d = map(int, input().split())
        adjacency_list[s].append(t)
        costs[(s, t)] = d
    dij = Dijkstra(max_v, adjacency_list, costs, start)
    dist = dij.single_source_shortest_path()
    for v in range(max_v):
        result = dist[v]
        if result < G_INF:
            print(result)
        else:
            print("INF")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python
from collections import defaultdict
import sys,csv,math,heapq
if sys.version_info[0]>=3: raw_input=input
INF=1<<30

def shortestPath(g,s,dist,prev):
	n = len(g)
	dist[s] = 0
	Q=[]
	heapq.heappush(Q,(0,-2,s))
	while Q:
		e=heapq.heappop(Q)
		if prev[e[2]]!=-1: continue
		prev[e[2]]=e[1]
		for f in g[e[2]]:
			if dist[f[2]]>e[0]+f[0]:
				dist[f[2]]=e[0]+f[0]
				heapq.heappush(Q,(e[0]+f[0],f[1],f[2]))

V,E,R=map(int,raw_input().split())
dist=[INF]*V
prev=[-1]*V
G=defaultdict(list)
for _ in range(E):
	s,t,d=map(int,raw_input().split())
	G[s].append([d,s,t])
	G[s].append([d,t,s])
shortestPath(G,R,dist,prev)
for e in dist:
	print('INF' if e==INF else e)

Submission status: Accepted

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, (dist[t], t))
for i in xrange(V):
    print dist[i] if dist[i]<INF else "INF"

Submission status: Accepted

Solution code:
import heapq

l = input().split()
V = int(l[0])
E = int(l[1])
r = int(l[2])

graph = [[] for _ in range(V)]
for i in range(E):
    l = input().split()
    graph[int(l[0])].append((int(l[2]),int(l[1])))

heap = [(0,r)]
dist = [float("inf") for _ in range(V)]
while heap:
    pop = heapq.heappop(heap)
    if dist[pop[1]] < pop[0]:
        continue
    dist[pop[1]] = pop[0]
    for (w,i) in graph[pop[1]]:
        if i!= pop[1] and w >= 0 and dist[i] == float("inf"):
            heapq.heappush(heap, (pop[0]+w, i))

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
from collections import defaultdict
from heapq import heappush, heappop

inf = float('inf')

def inf_matrix(n):
    return [[inf for i in range(n)] for j in range(n)]

def dijkstra(r, w, V):
    result = [inf] * V
    q = []
    heappush(q, (0, r))
    result[r] = 0
    while len(q) > 0:
        min_w, min_next = heappop(q)
        for weight, nxt in w[min_next]:
            if result[nxt] > min_w + weight:
                result[nxt] = min_w + weight
                heappush(q, (min_w + weight, nxt))

    return result


def main():
    V, E, r = map(int, input().split())
    w = defaultdict(list)
    for e in range(E):
        s, t, d = map(int, input().split())
        w[s].append((d, t))

    result = dijkstra(r, w, V)
    for i in range(V):
        if result[i] == inf:
            print('INF')
        else:
            print(result[i])

main()

Submission status: Accepted

Solution code:
V,E,r = map(int, input().split())
edge = []
for i in range(E):
    edge.append(list(map(int, input().split())))
inf = float('inf')
d = [inf for i in range(V)]
d[r] = 0
while True:
    update = False
    for i in range(E):
        e = edge[i]
        if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            update = True
    if update == False:
        break
for i in d:
    if i == inf:
        print('INF')
    else:
        print(i)