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: Memory Limit Exceeded

Solution code:
import sys

def dijkstra(nodes, start, matrix):
  defnode = [False] * (nodes)
  cost = [sys.maxint] * (nodes)
  cost[start] = 0
  node = start
  counter = 0
  while True:
    counter += 1
    if counter == nodes or node == sys.maxint:
      return cost
    defnode[node] = True
    for i in xrange(nodes):
      if defnode[i]:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(nodes):
      if defnode[i]:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    node = minnode

V,E,r = map(int, raw_input().split())
path = [[sys.maxint] * V for _ in xrange(V)]
for _ in xrange(E):
  s,t,d = map(int, raw_input().split())
  path[s][t] = d
cost = dijkstra(V, r, path)
for i in xrange(V):
  if cost[i] == sys.maxint:
    print "INF"
  else:
    print cost[i]

Submission status: Memory Limit Exceeded

Solution code:
import sys
import heapq

class Dijkstra(object):
  def dijkstra(self, adj, start, goal=None):
    num = len(adj)
    dist = [sys.maxint] * num
    prev = [sys.maxint] * num
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if dist[src] < prov_cost: continue
      for dest in range(num):
        cost = adj[src][dest]
        if cost != sys.maxint and 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] != sys.maxint:
      path.append(prev[dest])
      dest = prev[dest]
    return list(reversed(path))

V,E,r = map(int, raw_input().split())
path = [[sys.maxint] * V for _ in xrange(V)]
for _ in xrange(E):
  s,t,d = map(int, raw_input().split())
  path[s][t] = d
cost = Dijkstra().dijkstra(path, r)
for i in xrange(V):
  if cost[i] == sys.maxint:
    print "INF"
  else:
    print cost[i]

Submission status: Memory Limit Exceeded

Solution code:
import heapq as pq
inf = float("inf")
n,e,r = map(int, input().split())
M = [[inf for i in range(n)] for i in range(n)]

for i in range(e):
    s,t,d = map(int, input().split())
    M[s][t] = d
 
def dijkstra(s):
    color = [0] * n
    d = [inf] * n
    d[s] = 0
    H =[]
    pq.heappush(H, [0, s])
 
    while len(H) != 0:
        u2,u1 = pq.heappop(H)
        color[u1] = 1
        if d[u1] < u2:
            continue
        for v1,v2 in enumerate(M[u1]):
            if color[v1] == 1: continue
            if d[u1] + v2 < d[v1]:
                d[v1] = d[u1] + v2
                pq.heappush(H, [d[v1], v1])
    return d
 
d = dijkstra(r)
for i in d:
 if i == inf: print("INF")
 else: print(i)

Submission status: Memory Limit Exceeded

Solution code:
def main():
    [V,E,r]=input().split(" ")
    V=int(V)
    E=int(E)
    r=int(r)
    edgeset=[]
    for i in range(E):
        [s,t,d]=input().split(" ")
        edgeset.append([int(s),int(t),int(d)])
    '''read the edge information and put them to edgeset'''
    
    edgeset=binary_heap_sorting(edgeset)
    for i in range(V-len(edgeset)):
        edgeset.append([])

    setS=[]
    setV=[]
    setdist=[500000*10000+1 for i in range(V)]
    '''generate the sets for optimized vertices, unoptimized vertices, distance respectively'''

    setS.append(r)
    setV.append([r,0])
    setdist[r]=0
    '''initiating data'''

    for i in range(9999999999):
        nowvert=setS[-1]
        for j in range(len(edgeset[nowvert])):
            newdist=edgeset[nowvert][j][2]+setdist[nowvert]
            olddist=setdist[edgeset[nowvert][j][1]]
            '''calculating the new distance including the on process vertices'''
            if(newdist<olddist):
                setdist[edgeset[nowvert][j][1]]=newdist
                setV=binary_heap_add(setV,newdist,edgeset[nowvert][j][1])
            '''making comparision to determin which to stay'''
        if(setV==[[r,0]]):
            break
        setS.append(setV[1][0])
        setV=binary_heap_deletion(setV)
        '''find the next on process vertice'''
                    
    for i in range(V):
        if(setdist[i]==500000*10000+1):
            print('INF')
        else:
            print(setdist[i])
    '''data output'''
    
    return 0

def binary_heap_building(dataset):
    for i in [len(dataset)-x-1 for x in range(len(dataset))]:
        if(dataset[i][1]<dataset[int(i/2)][1]):
            trans=dataset[i]
            dataset[i]=dataset[int(i/2)]
            dataset[int(i/2)]=trans
    return dataset

def binary_heap_sorting(dataset):
    lenth=len(dataset)
    dataset.insert(0,[-1,-1])
    dataset=binary_heap_building(dataset)
    parameter=0
    ndataset=[[]]

    for i in range(lenth):
        if(parameter!=dataset[1][0]):
            for i in range(dataset[1][0]-parameter):
                ndataset.append([])
            parameter=dataset[1][0]
            ndataset[parameter].append(dataset[1])
        else:
            ndataset[parameter].append(dataset[1])
        dataset=binary_heap_deletion(dataset)
            
    return ndataset

    
def binary_heap_change(dataset,newdata,position):
    biposition=[a[0] for a in dataset].index(position)
    dataset[biposition][1]=newdata
    for i in range(999999):
        if(newdata<dataset[int(biposition/2)][1]):
            trans=dataset[biposition]
            dataset[biposition]=dataset[int(biposition/2)]
            dataset[int(biposition/2)]=trans
            biposition=int(biposition/2)
            
        elif(biposition*2<len(dataset) and biposition*2+1<len(dataset) and (newdata>dataset[biposition*2][1] or newdata>dataset[biposition*2+1][1])):
            if(dataset[biposition*2][1]>=dataset[biposition*2+1][1]):
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2+1]
                dataset[biposition*2+1]=trans
                biposition=biposition*2+1
            else:
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2]
                dataset[biposition*2]=trans
                biposition=biposition*2
        else:
            break
    return dataset

    
    
def binary_heap_deletion(dataset):
    newdata=dataset[-1][1]
    trans=dataset[1]
    dataset[1]=dataset[-1]
    dataset[-1]=trans
    dataset.pop(-1)
    biposition=1
    for i in range(999999):
        if(biposition*2<len(dataset) and biposition*2+1<len(dataset) and (newdata>dataset[biposition*2][1] or newdata>dataset[biposition*2+1][1])):
            if(dataset[biposition*2][1]>=dataset[biposition*2+1][1]):
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2+1]
                dataset[biposition*2+1]=trans
                biposition=biposition*2+1
            else:
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2]
                dataset[biposition*2]=trans
                biposition=biposition*2
        else:
            break
    return dataset

def binary_heap_add(dataset,newdata,position):
    dataset.append([position,newdata])
    biposition=len(dataset)-1
    for i in range(999999):
        if(newdata<dataset[int(biposition/2)][1]):
            trans=dataset[biposition]
            dataset[biposition]=dataset[int(biposition/2)]
            dataset[int(biposition/2)]=trans
            biposition=int(biposition/2)
        else:
            break
    return dataset

    
    
main()

Submission status: Memory Limit Exceeded

Solution code:
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    return d

result = Dijkstra(r, vertex)
for i in range(vertex):
    if i == r:
        result[i] = 0
    if result[i] == infty:
        result[i] = "INF"
    print(result[i])

Submission status: Memory Limit Exceeded

Solution code:
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    return d

result = Dijkstra(r, vertex)

for i in range(vertex):
    if i == r:
        result[i] = 0
    if result[i] == infty:
        result[i] = "INF"
    print(result[i])

Submission status: Memory Limit Exceeded

Solution code:
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    d[root] = 0
    return d

result = Dijkstra(r, vertex)

for i in range(vertex):
    if result[i] == infty:
        result[i] = "INF"
    print(result[i])

Submission status: Memory Limit Exceeded

Solution code:
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    #del visited_order
    #del label
    #del D
    #del min_cost

    d[root] = 0
    return d

result = Dijkstra(r, vertex)

for i in range(vertex):
    if result[i] == infty:
        result[i] = "INF"
    print(result[i])

Submission status: Memory Limit Exceeded

Solution code:
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    d[root] = 0
    D[root] = d

Dijkstra(r, vertex)

for i in range(vertex):
    if D[r][i] == infty:
        print("INF")
    else:
        print(D[r][i])

Submission status: Memory Limit Exceeded

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] > -1:
				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 = [[-1]*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: Memory Limit Exceeded

Solution code:
inf = 0x11111111
def solve(G,start):
	cost = [inf]*V
	visited = [0]*V
	cost[start] = 0
	while 1:
		visited[start] = 1
		next = -1
		min = inf
		for i in range(V):
			if visited[i]: continue
			if G[start][i] > -1:
				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 = [[-1]*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: Accepted

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:
            cur_cost, cur_vertex = hp.heappop(que)
            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))


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

Solution code:
import sys
from heapq import heappush, heappop


class Dijkstra:

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

    def __init__(self, V):
        self._node = V
        self._graph = [[] for i in range(self._node)]
        self.inf = 10 ** 10
        self.dist = [self.inf for i in range(self._node)]

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

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


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

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop


class Dijkstra:

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

    def __init__(self, V, INF):
        self._node = V
        self._graph = [[] for i in range(self._node)]
        self.inf = INF
        self.dist = [self.inf for i in range(self._node)]

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

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


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

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop


class Dijkstra:

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

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

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

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


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

Submission status: Accepted

Solution code:
import sys
import queue


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

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

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

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


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

Submission status: Accepted

Solution code:
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:
        s,t,w = x
        if d[t] > d[s] + w:
            count += 1
            d[t] = d[s] + w
    if count == 0:
        break
 
for x in d:
    if x == float('inf'):
        print('INF')
    else:
        print(x)

Submission status: Accepted

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):
  count = 0
  for s,v,c in edges:
    if d[v] > d[s]+c:
      count += 1
      d[v] = d[s]+c
  if count == 0:
    break

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
v,e,r = map(int,input().split())
edges=[[] for i in range(v)]
d = [float('INF')]*v

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

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

while que:
  c, u = heappop(que)
  for v, s in edges[u]:
    if d[v] > s + c:
      d[v] = s + c
      heappush(que,(d[v],v))
for i in d:
  if i == float('inf'):
    print('INF')
  else:
    print(i)

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:
# AOJ GRL_1_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

from heapq import heappush, heappop

INF = 10000000000

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

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

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

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

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

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