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  s 0  t 0  d 0  s 1  t 1  d 1 : 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.  s i and t i represent source and target vertices of i -th edge (directed) and d i represents the cost of the i -th edge. Output Print the costs of SSSP in the following format.  c 0  c 1 : 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 ≤ d i ≤ 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

Solution (Python):
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"

Solution (Python):
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

Solution (Python):
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

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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')

Solution (Python):



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

Solution (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)

Solution (Python):
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"

Solution (Python):
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)

Solution (Python):

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

Solution (Python):
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)

Solution (Python):
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 
        self.prev = [-1] * self.V 
        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')

Solution (Python):
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  
        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]))

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

Solution (Python):
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  
        self.prev = [-1] * self.G.V  
        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

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

Solution (Python):
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 Node:
    def __init__(self, v, cost):
        self.v, self.cost = v, cost

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


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

    def dijkstra(self, start, goal=None):
        que = list()
        self.dist = [self.INF] * self.G.V  
        self.prev = [-1] * self.G.V  
        self.dist[start] = 0
        heapq.heappush(que, 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, Node(e.dst, self.dist[e.dst]))
                    self.prev[e.dst] = n.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])

Solution (Python):
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  
        self.prev = [-1] * self.G.V  
        self.dist[start] = 0
        heapq.heappush(que, (0, start))

        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.G.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.dist[e.dst], 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])

Solution (Python):
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 
        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')

Solution (Python):



"""
input:
4 6 1
0 1 1
0 2 4
2 0 1
1 2 2
3 1 1
3 2 5

output:
3
0
2
INF
"""

import sys
import heapq as hp
from math import isinf

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
    return init_adj_table


def dijkstra_path_heap():
    
    distance[root] = 0
    path_heap = []
    
    hp.heappush(path_heap, (0, root))

    while path_heap:
        current = hp.heappop(path_heap)[1]

        color[current] = BLACK

        for adj, cost in adj_table[current].items():
            if color[adj] is not BLACK:
                
                alt_path = distance[current] + cost
                if alt_path < distance[adj]:
                    
                    distance[adj] = alt_path
                    
                    hp.heappush(path_heap, (alt_path, adj))
                    color[adj] = GRAY
                    parents[adj] = current

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    

    distance = [float('inf')] * vertices
    parents = [-1] * vertices
    color = [WHITE] * vertices
    init_adj_table = tuple(dict() for _ in range(vertices))

    adj_table = generate_adj_table(v_info)
    ans = dijkstra_path_heap()

    print('\n'.join(('INF' if isinf(ele) else str(ele) for ele in ans)))

Solution (Python):



"""
input:
4 6 1
0 1 1
0 2 4
2 0 1
1 2 2
3 1 1
3 2 5

output:
3
0
2
INF
"""

import sys
import heapq as hp
from math import isinf

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
    return init_adj_table


def dijkstra_path_heap():
    
    distance[root] = 0
    path_heap = []
    
    hp.heappush(path_heap, (0, root))

    while path_heap:
        current = hp.heappop(path_heap)[1]

        color[current] = BLACK

        for adj, cost in adj_table[current].items():
            if color[adj] is not BLACK:
                
                alt_path = distance[current] + cost
                if alt_path < distance[adj]:
                    
                    distance[adj] = alt_path
                    
                    hp.heappush(path_heap, (alt_path, adj))
                    color[adj] = GRAY
                    parents[adj] = current

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    

    distance = [float('inf')] * vertices
    parents = [-1] * vertices
    color = [WHITE] * vertices
    init_adj_table = tuple(dict() for _ in range(vertices))

    adj_table = generate_adj_table(v_info)
    ans = dijkstra_path_heap()

    
    for ele in ans:
        if isinf(ele):
            print("INF")
        else:
            print(ele)

Solution (Python):
import heapq

maxd = float('inf')
nv, ne, r = [int(n) for n in input().split(' ')]
vertices = {k: {} for k in range(nv)}
for i in range(ne):
    s, t, w = [int(n) for n in input().split(' ')]
    vertices[s][t] = w

q = []
heapq.heappush(q, (0, r))

dist = {v: maxd for v in vertices}
dist[r] = 0

while len(q):
    u = heapq.heappop(q)[1]

    for v in vertices[u]:
        alt = dist[u] + vertices[u][v]
        if alt < dist[v]:
            dist[v] = alt
            heapq.heappush(q, (alt, v))

[print(d) if d < maxd else print("INF") for v, d in dist.items()]

Solution (Python):
import heapq

nv, ne, r = map(int, input().split(' '))
vertices = [[] for i in range(nv)]
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    vertices[s].append((t, w))

q = []
heapq.heappush(q, (0, r))

dist = [float('inf')] * nv
dist[r] = 0

while len(q):
    u = heapq.heappop(q)[1]

    for t, w in vertices[u]:
        alt = dist[u] + w
        if alt < dist[t]:
            dist[t] = alt
            heapq.heappush(q, (alt, t))

[print(d) if d < float('inf') else print("INF") for d in dist]