Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Single Source Shortest Path

For a given weighted graph $G = (V, E)$, find the shortest path from a source to each vertex. For each vertex $u$, print the total weight of edges on the shortest path from vertex $0$ to $u$.

Input

  In the first line, an integer $n$ denoting the number of vertices in $G$ is given. In the following $n$ lines, adjacency lists for each vertex $u$ are respectively given in the following format:

$u$ $k$ $v_1$ $c_1$ $v_2$ $c_2$ ... $v_k$ $c_k$

  Vertices in $G$ are named with IDs $0, 1, ..., n-1$. $u$ is ID of the target vertex and $k$ denotes its degree. $v_i (i = 1, 2, ... k)$ denote IDs of vertices adjacent to $u$ and $c_i$ denotes the weight of a directed edge connecting $u$ and $v_i$ (from $u$ to $v_i$).

Output

  For each vertex, print its ID and the distance separated by a space character in a line respectively. Print in order of vertex IDs.

Constraints

$1 \leq n \leq 100$

$0 \leq c_i \leq 100,000$

$|E| \leq 10,000$

All vertices are reachable from vertex $0$

Sample Input 1

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

Sample Output 1

0 0
1 2
2 2
3 1
4 3

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



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


Sample output:
0 0
1 2
2 2
3 1
4 3

Submission status: Accepted

Solution code:
n = input()
inf = 1000000000
M = [[inf for i in range(n)] for i in range(n)]
for i in range(n):
  str = map(int, raw_input().split())
  u = str[0]
  k = str[1]
  for j in range(k):
    v = str[2+2*j]
    c = str[3+2*j]
    M[u][v] = c
d = [inf for i in range(n)]
color = [0 for i in range(n)]
 
d[0] = 0
color[0] = 1
 
while 1:
  minv = inf
  u = -1
  for i in range(n):
    if minv>d[i] and color[i]!=2:
      u = i
      minv = d[i]
  if u == -1:
    break
  color[u] = 2
  for v in range(n):
    if color[v]!=2 and M[u][v]!=inf:
      if d[v]>d[u]+M[u][v]:
        d[v] = d[u] + M[u][v]
        color[v] = 1
for i in range(n):
  if d[i]==inf:
    print '%d -1' % i
  else:
    print '%d %d' % (i, d[i])

Submission status: Accepted

Solution code:
MAX = 100
INF = 1000000
WHITE = 0
GRAY = 1
BLACK = 2
n = int(raw_input())

M = [[INF for i in range(n)]for j in range(n)]
d = [INF for i in range(MAX)]
Color = [WHITE for i in range(MAX)]
for i in range(n):
    tmp = map(int,raw_input().split())
    u = tmp[0]
    k = tmp[1]
    for j in range(1, k + 1):
        v = tmp[j * 2]
        c = tmp[j * 2 + 1]
        M[u][v] = c

#def dijkstra():
d[0] = 0
Color[0] = GRAY
    
while True:
    minv = INF
    u = -1
    for i in range(n):
        if minv > d[i] and Color[i] != BLACK:
            u = i
            minv = d[i]
    if u == -1:
        break
    Color[u] = BLACK
    for v in range(n):
        if Color[v] != BLACK and M[u][v] != INF:
            if d[v] > d[u] + M[u][v]:
                d[v] = d[u] + M[u][v]
                Color[v] = GRAY
for i in range(n):
    print i,
    if d[i] == INF:
        print -1
    else:
        print d[i]

Submission status: Accepted

Solution code:
import heapq

n = int(input())
edges = [None] * n
for _ in range(n):
    l = list(map(int, input().split()))
    edges[l[0]] = set((c, j) for j, c in (l[i:i + 2] for i in range(2, l[1] * 2 + 2, 2)))

min_costs = [0] * n
visited = [False] * n
visited[0] = True
queue = list(edges[0])
heapq.heapify(queue)

while queue:
    total_cost, vertex = heapq.heappop(queue)
    if visited[vertex]:
        continue
    visited[vertex] = True
    min_costs[vertex] = total_cost
    for cost, vertex2 in edges[vertex]:
        if not visited[vertex2]:
            heapq.heappush(queue, (total_cost + cost, vertex2))

for r in enumerate(min_costs):
    print(*r)

Submission status: Accepted

Solution code:

WHITE = 0
GRAY = 1
BLACK = 2

n = int(raw_input())
M = [ [-1] * n for _ in xrange(n)]
color = [WHITE] * n
d = [float('inf')] * n

for i in xrange(n):
    a = map(int, raw_input().split())
    for j in xrange(a[1]):
        M[a[0]][a[2*(j+1)]] = a[2*(j+1)+1]

def dijkstra():
    d[0] = 0

    while True:
        mincost = float('inf')
        for i in xrange(n):
            if color[i] != BLACK and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == float('inf'):
            break

        color[u] = BLACK

        for v in xrange(n):
            if color[v] != BLACK and M[u][v] >= 0:
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]
                    color[v] = GRAY

    for i in xrange(n):
        print "{} {}".format(i, d[i])

    return 0

def main():
    dijkstra()
    return 0

main()

Submission status: Accepted

Solution code:
infty = 10**21
white = 0
gray = 1
black = 2
n = input()
m = [[infty for i in xrange(n)] for j in xrange(n)]
l = [[0 for i in xrange(n)] for j in xrange(n)]
d = [0 for i in xrange(n)]
color = [0 for i in xrange(n)]
def dijkstra():
    
    

    for i in xrange(n):
        d[i] = infty
        color[i] = white


    d[0] = 0
    color[0] = gray
    while True:
        minv = infty
        u = -1
        for i in xrange(n):
            if minv > d[i] and color[i] != black:
                u = i
                minv = d[i]
        if u == -1:
            break
        color[u] = black
        for v in xrange(n):
            if color[v] != black and m[u][v] != infty:
                if d[v] > d[u] + m[u][v]:
                    d[v] = d[u] + m[u][v]
                    color[v] = gray

    for i in xrange(n):
        if d[i] == infty:
            print i,-1
        else:
            print i,d[i]



for i in xrange(n):
    l[i] = map(int,raw_input().split())
    u = l[i][0]
    k = l[i][1]
    for j in xrange(2,k*2+2,2):
        v = l[i][j]
        c = l[i][j+1]
        m[u][v] = c

dijkstra()

Submission status: Accepted

Solution code:
import heapq


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

    def __init__(self, V, E, start, 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.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
        heapq.heappush(que, (0, start))

        while len(que) > 0:
            dist, fr = heapq.heappop(que)
            if self.distance[fr] < dist:
                continue
            for to, cost in self.E[fr]:
                if self.distance[fr] + cost < self.distance[to]:
                    self.distance[to] = self.distance[fr] + cost
                    heapq.heappush(que, (self.distance[to], to))
                    self.prev[to] = fr

    def getPath(self, end):
        path = [end]
        while self.prev[end] != -1:
            end = self.prev[end]
        return path[::-1]
V = int(input())
edge = [[] for _ in range(V)]
for _ in range(V):
    u, _, *e = map(int, input().split())
    for t, d in zip(e[::2], e[1::2]):
        edge[u].append((t, d))

sp = ShortestPath(V, edge, 0)
for i, d in enumerate(sp.distance):
    print(i, d)

Submission status: Accepted

Solution code:
def dijkstra(n):
    inf = 10 ** 6 + 1
    dist = [0] + [inf] * (n - 1)
    visited = [False] * n

    while not all(visited):
        dmin = inf
        for i, (d, v) in enumerate(zip(dist, visited)):
            if dmin > d and not v:
                dmin, u = d, i
        visited[u] = True
        for (v, c) in edge[u]:
            if dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
    return dist

n = int(input())
edge = [[]] * n
for _ in range(n):
    l = list(map(int, input().split()))
    edge[l[0]] = (e for e in zip(l[2::2], l[3::2]))
for i, c in enumerate(dijkstra(n)):
    print(i, c)

Submission status: Accepted

Solution code:
def dijkstra(s):
    global d
    color=[0]*n
    d=[float('inf')]*n
    d[s]=0
    while True:
        mincost=float('inf')
        for i in xrange(n):
            if color[i]!=2 and d[i]<mincost:
                mincost=d[i]
                u=i
        if mincost==float('inf'):
            break
        color[u]=2
        for v in xrange(n):
            if color[v]!=2 and m[u][v]!=0:
                if d[u]+m[u][v]<d[v]:
                    d[v]=d[u]+m[u][v]
                    color[v]=1

if __name__=='__main__':
    n=input()
    m=[[0]*n for i in xrange(n)]
    for i in xrange(n):
        en=map(int,raw_input().split())
        for j in xrange(2*en[1]):
            if j%2==0:
                enid=en[2+j]
            else:
                m[en[0]][enid]=en[2+j]
    dijkstra(0)
    for i in xrange(n):
        print i,d[i]

Submission status: Accepted

Solution code:
import sys

def dijkstra(W, n):
    U = [i for i in range(1, n)]
    D = [W[0][i] for i in range(n)]
    D[0] = 0

    while len(U) != 0:
        mind, minu = 200001, -1
        for u in U:
            if D[u] <= mind:
                mind, minu = D[u], u
        U.remove(minu)
        for i in range(1, n):
            D[i] = min(D[i], D[minu] + W[minu][i])

    return D

lines = sys.stdin.readlines()
n = int(lines.pop(0))

W = [[200001] * n for _ in range(n)]
for line in lines:
    l = map(int, line.split())
    for i in range(l[1]):
        W[l[0]][l[2 * i + 2]] = l[2 * i + 3]

D = dijkstra(W, n)

for i in range(n):
    print i, D[i]

Submission status: Accepted

Solution code:
from queue import PriorityQueue

def sssp(adj_list):
    n = len(adj_list)
    d = [None]*n
    pq = PriorityQueue()
    pq.put((0, 0)) # d, v

    while(not pq.empty()):
        d_v, v = pq.get()
        if d[v] is not None:
            continue
        d[v] = d_v
        for u, c_vu in adj_list[v]:
            pq.put((d[v]+c_vu, u))

    return d


if __name__ == '__main__':
    n = int(input())
    adj_list = []
    for _ in range(n):
        adj_list.append([])

    for _ in range(n):
        l = list(map(int, input().rstrip().split(' ')))
        u = l[0]
        k = l[1]
        adj_list_for_u = []
        for v, c in zip(l[2::2], l[3::2]):
            adj_list_for_u.append((v,c))
        adj_list[u] = adj_list_for_u

    d = sssp(adj_list)
    for u, d_u in zip(range(n), d):
        print (u, d_u)

Submission status: Accepted

Solution code:
n = int(input())

adj = [[100001 for j in range(n)] for i in range(n)]

for u in range(n):
    x = list(map(int, input().split()))
    for v, c in zip(x[2::2], x[3::2]):
        adj[u][v] = c

isVisited = [False] * n

distance = [9900001] * n


def dijkstra(s):
    distance[s] = 0

    while True:
        mincost = 9900001
        for i in range(n):
            if (not isVisited[i]) and (distance[i] < mincost):
                mincost = distance[i]
                u = i

        if mincost == 9900001:
            break

        isVisited[u] = True

        for v in range(n):
            weight_uv = adj[u][v]
            if (not isVisited[v]) and (weight_uv != 100001):
                t_d = distance[u] + weight_uv
                if t_d < distance[v]:
                    distance[v] = t_d



dijkstra(0)

for v, d in enumerate(distance):
    print(v, d)

Submission status: Accepted

Solution code:
n = int(input())

adj = [[100001 for j in range(n)] for i in range(n)]

for u in range(n):
    x = list(map(int, input().split()))
    for v, c in zip(x[2::2], x[3::2]):
        adj[u][v] = c

unvisited = {v for v in range(n)}

distance = [9900001] * n


def dijkstra(s):
    distance[s] = 0

    while True:
        mincost = 9900001
        for i in unvisited:
            if distance[i] < mincost:
                mincost = distance[i]
                u = i

        if mincost == 9900001:
            break

        unvisited.discard(u)

        for v in unvisited:
            weight_uv = adj[u][v]
            if weight_uv != 100001:
                t_d = distance[u] + weight_uv
                if t_d < distance[v]:
                    distance[v] = t_d



dijkstra(0)

for v, d in enumerate(distance):
    print(v, d)

Submission status: Accepted

Solution code:
n = int(input())

adj = [[100001 for j in range(n)] for i in range(n)]

for u in range(n):
    x = list(map(int, input().split()))
    for v, c in zip(x[2::2], x[3::2]):
        adj[u][v] = c

unvisited = [v for v in range(n)]

distance = [9900001] * n


def dijkstra(s):
    distance[s] = 0

    while True:
        mincost = 9900001
        for i in unvisited:
            if distance[i] < mincost:
                mincost = distance[i]
                u = i

        if mincost == 9900001:
            break

        unvisited.remove(u)

        for v in unvisited:
            weight_uv = adj[u][v]
            if weight_uv != 100001:
                t_d = distance[u] + weight_uv
                if t_d < distance[v]:
                    distance[v] = t_d



dijkstra(0)

for v, d in enumerate(distance):
    print(v, d)

Submission status: Accepted

Solution code:
trial = int(input())
graph = []
for t in range(trial):
    graph.append([int(n) for n in input().split(" ")])
root = []
ans = []
stack = [[0,0]]
cnt = 0
while len(stack) > 0:
    index,out = stack[0][0],stack[0][1]
    for get in range(graph[index][1]):
        if graph[index][get*2 + 2] not in root:
            stack.append([graph[index][get*2 +2],graph[index][get*2 +3] + out ])
    if stack[0][0] not in root:
        root.append(stack[0][0])
        ans.append([stack[0][0],stack[0][1]])
    stack.pop(0)
    stack = sorted(stack,key=lambda x:x[1])
ans = sorted(ans,key=lambda x:x[0])
for a in range(trial):
    print(str(ans[a][0]) + " " + str(ans[a][1]))

Submission status: Accepted

Solution code:
import heapq

def dijkstra(s,g,c):
    d=[float('inf')]*n
    d[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        if d[u]<t:
            continue
        for v in g[u]:
            if d[u]+c[u][v]<d[v]:
                d[v]=d[u]+c[u][v]
                heapq.heappush(pq,[d[v],v])
    return d

n=int(raw_input())
g=[[] for _ in xrange(n)]
cost=[[10**9+5]*n for i in xrange(n)]

for i in xrange(n):
    en=map(int,raw_input().split())
    u=en[0];k=en[1];v=en[2:-1:2];c=en[3::2]
    for j in xrange(k):
        g[u].append(v[j])
        cost[u][v[j]]=c[j]

pq=[]
dist=dijkstra(0,g,cost)

for i in xrange(n):
    print i,dist[i]

Submission status: Accepted

Solution code:
def relax(u, v, w):
    if D[u] + w < D[v]:
        D[v] = D[u] + w
        P[v] = u

INF = float('inf')
N = int(input())
D = [INF for i in range(N)]
P = [None for i in range(N)]
C = ['w' for i in range(N)]
D[0] = 0

G = [[INF for j in range(N)] for i in range(N)]
for i in range(N):
    x = list(map(int, input().split()))
    g = x[2:]
    for j, n in enumerate(g):
        if j % 2 == 0:
            G[i][n] = g[j + 1]


while True:
    mincost = INF
    u = -1
    for i in range(N):
        if C[i] != 'b' and D[i] < mincost:
            mincost = D[i]
            u = i
    if u == -1:
        break
    C[u] = 'b'
    for v, w in enumerate(G[u]):
        if w != INF and C[v] != 'b':
            relax(u, v, w)
            C[v] = 'g'

for i, d in enumerate(D):
    print('{0} {1}'.format(i, d))

Submission status: Accepted

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

import sys

WHITE, GRAY, BLACK = 0, 1, 2
D_MAX = int(1e7 + 1)


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_index = int(v_detail[0])
        v_adj_length = int(v_detail[1])
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == v_adj_length * 2
        for j in range(0, v_adj_length * 2, 2):
            init_adj_matrix[v_index][v_adj_list[j]] = int(v_adj_list[j + 1])

    return init_adj_matrix


def dijkstra_path():
    path_list[0] = 0

    while True:
        min_cost = D_MAX
        current_vertex = None
        for i in range(vertices_num):
            if color[i] is not BLACK and path_list[i] < min_cost:
                min_cost = path_list[i]
                current_vertex = i

        if min_cost == D_MAX:
            break

        color[current_vertex] = BLACK

        for v in range(vertices_num):
            current_v_weight = adj_matrix[current_vertex].get(str(v), -1)
            if current_v_weight < 0:
                continue
            elif color[v] is not BLACK:
                if path_list[current_vertex] + current_v_weight < path_list[v]:
                    path_list[v] = path_list[current_vertex] + current_v_weight
                    parent_list[v] = current_vertex
                    color[v] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = list(map(lambda x: x.split(), _input[1:]))
    # assert len(init_vertices_table) == vertices_num

    parent_list, path_list = [-1] * vertices_num, [D_MAX] * vertices_num
    color = [WHITE] * vertices_num
    init_adj_matrix = [{} for _ in range(vertices_num)]
    adj_matrix = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for j in range(vertices_num):
        print(j, ans[j])

Submission status: Accepted

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

import sys

WHITE, GRAY, BLACK = 0, 1, 2
D_MAX = int(1e7 + 1)


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_index = int(v_detail[0])
        v_adj_length = int(v_detail[1])
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == v_adj_length * 2
        for j in range(0, v_adj_length * 2, 2):
            init_adj_matrix[v_index][v_adj_list[j]] = int(v_adj_list[j + 1])

    return init_adj_matrix


def dijkstra_path():
    path_list[0] = 0

    while True:
        min_cost = D_MAX
        current_vertex = None
        for i in range(vertices_num):
            if color[i] is not BLACK and path_list[i] < min_cost:
                min_cost = path_list[i]
                current_vertex = i

        if min_cost == D_MAX:
            break

        color[current_vertex] = BLACK

        for adj_vertex in range(vertices_num):
            current_v_weight = adj_matrix[current_vertex].get(str(adj_vertex), -1)
            if current_v_weight < 0:
                continue
            elif color[adj_vertex] is not BLACK:
                if path_list[current_vertex] + current_v_weight < path_list[adj_vertex]:
                    path_list[adj_vertex] = path_list[current_vertex] + current_v_weight
                    parent_list[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = list(map(lambda x: x.split(), _input[1:]))
    # assert len(init_vertices_table) == vertices_num

    parent_list, path_list = [-1] * vertices_num, [D_MAX] * vertices_num
    color = [WHITE] * vertices_num
    init_adj_matrix = tuple({} for _ in range(vertices_num))
    adj_matrix = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for j in range(vertices_num):
        print(j, ans[j])

Submission status: Accepted

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

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

output:
0 0
1 2
2 2
3 1
4 3
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2
D_MAX = int(1e7 + 1)


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_index = int(v_detail[0])
        v_adj_length = int(v_detail[1])
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == v_adj_length * 2
        for j in range(0, v_adj_length * 2, 2):
            init_adj_matrix[v_index][v_adj_list[j]] = int(v_adj_list[j + 1])

    return init_adj_matrix


def dijkstra_path():
    # path search init
    start_vertex_index = 0
    path_list[start_vertex_index] = 0
    path_heap = []
    # heapq: compare by tuple[0]
    hp.heappush(path_heap, (path_list[start_vertex_index], start_vertex_index))
    while len(path_heap) >= 1:
        current_vertex = hp.heappop(path_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex in range(vertices_num):
            current_adj_weight = adj_matrix[current_vertex].get(str(adj_vertex), -1)
            if current_adj_weight < 0:
                continue
            elif color[adj_vertex] is not BLACK:
                # d[u] + w[u,v]
                alt_path = path_list[current_vertex] + current_adj_weight
                if alt_path < path_list[adj_vertex]:
                    # update path_list
                    path_list[adj_vertex] = alt_path
                    # update heap
                    hp.heappush(path_heap, (alt_path, adj_vertex))
                    parent_list[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = list(map(lambda x: x.split(), _input[1:]))
    # assert len(init_vertices_table) == vertices_num

    parent_list, path_list = [-1] * vertices_num, [D_MAX] * vertices_num
    color = [WHITE] * vertices_num
    init_adj_matrix = tuple(dict() for _ in range(vertices_num))
    adj_matrix = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for i, v in enumerate(ans):
        print(i, v)

Submission status: Accepted

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

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

output:
0 0
1 2
2 2
3 1
4 3
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2
D_MAX = int(1e7 + 1)


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_index = int(v_detail[0])
        v_adj_length = int(v_detail[1])
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == v_adj_length * 2
        for j in range(0, v_adj_length * 2, 2):
            init_adj_matrix[v_index][int(v_adj_list[j])] = int(v_adj_list[j + 1])

    return init_adj_matrix


def dijkstra_path():
    # path search init
    start_vertex_index = 0
    path_list[start_vertex_index] = 0
    path_heap = []
    # heapq: compare by tuple[0]
    hp.heappush(path_heap, (path_list[start_vertex_index], start_vertex_index))
    while len(path_heap) >= 1:
        current_vertex_index = hp.heappop(path_heap)[1]

        color[current_vertex_index] = BLACK

        for adj_vertex_index in range(vertices_num):
            current_adj_weight = adj_matrix[current_vertex_index].get(adj_vertex_index, -1)
            if current_adj_weight < 0:
                continue
            elif color[adj_vertex_index] is not BLACK:
                # d[u] + w[u,v]
                alt_path = path_list[current_vertex_index] + current_adj_weight
                if alt_path < path_list[adj_vertex_index]:
                    # update path_list
                    path_list[adj_vertex_index] = alt_path
                    # update heap
                    hp.heappush(path_heap, (alt_path, adj_vertex_index))
                    parent_list[adj_vertex_index] = current_vertex_index
                    color[adj_vertex_index] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = list(map(lambda x: x.split(), _input[1:]))
    # assert len(init_vertices_table) == vertices_num

    parent_list, path_list = [-1] * vertices_num, [D_MAX] * vertices_num
    color = [WHITE] * vertices_num
    init_adj_matrix = tuple(dict() for _ in range(vertices_num))
    adj_matrix = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for i, v in enumerate(ans):
        print(i, v)

Submission status: Accepted

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

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

output:
0 0
1 2
2 2
3 1
4 3
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2
D_MAX = int(1e7 + 1)


def generate_adj_matrix(v_info):
    for each in v_info:
        v_index, v_adj_length, *v_adj_list = map(int, each)
        # assert len(v_adj_list) == v_adj_length * 2
        for pair in zip(v_adj_list[::2], v_adj_list[1::2]):
            init_adj_matrix[v_index][pair[0]] = pair[1]

    return init_adj_matrix


def dijkstra_path():
    # path search init
    path_list[init_vertex_index] = 0
    path_heap = []
    # heapq: rank by tuple[0], here ranked by d[u]
    hp.heappush(path_heap, (0, init_vertex_index))
    while len(path_heap) >= 1:
        current_vertex_index = hp.heappop(path_heap)[1]

        color[current_vertex_index] = BLACK

        for adj_vertex_index in range(vertices_num):
            current_adj_weight = adj_table[current_vertex_index].get(adj_vertex_index, -1)
            if current_adj_weight < 0:
                continue
            elif color[adj_vertex_index] is not BLACK:
                # alt: d[u] + w[u,v]
                alt_path = path_list[current_vertex_index] + current_adj_weight
                if alt_path < path_list[adj_vertex_index]:
                    # update path_list
                    path_list[adj_vertex_index] = alt_path
                    # update heap
                    hp.heappush(path_heap, (alt_path, adj_vertex_index))
                    parent_list[adj_vertex_index] = current_vertex_index
                    color[adj_vertex_index] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = map(lambda x: x.split(), _input[1:])
    # assert len(init_vertices_table) == vertices_num

    parent_list, path_list = [-1] * vertices_num, [D_MAX] * vertices_num
    color = [WHITE] * vertices_num
    init_adj_matrix = tuple(dict() for _ in range(vertices_num))
    init_vertex_index = 0

    adj_table = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for i, v in enumerate(ans):
        print(i, v)

Submission status: Accepted

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

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

output:
0 0
1 2
2 2
3 1
4 3
"""

import sys

WHITE, GRAY, BLACK = 0, 1, 2
D_MAX = int(1e7 + 1)


def generate_adj_matrix(v_info):
    for each in v_info:
        v_index, v_adj_length, *v_adj_list = map(int, each)
        # assert len(v_adj_list) == v_adj_length * 2
        for pair in zip(v_adj_list[::2], v_adj_list[1::2]):
            init_adj_matrix[v_index][pair[0]] = pair[1]

    return init_adj_matrix


def dijkstra_path():
    path_list[0] = 0

    while True:
        min_cost = D_MAX
        current_vertex_index = None
        for i in range(vertices_num):
            if color[i] is not BLACK and path_list[i] < min_cost:
                min_cost = path_list[i]
                current_vertex_index = i

        if min_cost == D_MAX:
            break

        color[current_vertex_index] = BLACK
        current_vertex_index_info = adj_table[current_vertex_index]
        for adj_vertex_index in current_vertex_index_info.keys():
            current_adj_weight = current_vertex_index_info.get(adj_vertex_index)
            if color[adj_vertex_index] is not BLACK:
                alt_path = path_list[current_vertex_index] + current_adj_weight
                if alt_path < path_list[adj_vertex_index]:
                    # update path_list
                    path_list[adj_vertex_index] = alt_path
                    parent_list[adj_vertex_index] = current_vertex_index
                    color[adj_vertex_index] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = (map(lambda x: x.split(), _input[1:]))
    # assert len(init_vertices_table) == vertices_num

    parent_list, path_list = [-1] * vertices_num, [D_MAX] * vertices_num
    color = [WHITE] * vertices_num
    init_adj_matrix = tuple(dict() for _ in range(vertices_num))
    adj_table = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for j in range(vertices_num):
        print(j, ans[j])

Submission status: Accepted

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

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

output:
0 0
1 2
2 2
3 1
4 3
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        v_index, v_adj_length, *v_adj_list = map(int, each)
        # assert len(v_adj_list) == v_adj_length * 2
        for pair in zip(v_adj_list[::2], v_adj_list[1::2]):
            init_adj_table[v_index][pair[0]] = pair[1]

    return init_adj_table


def dijkstra_path_heap():
    # path search init
    distance[init_vertex] = 0
    path_heap = []
    # heapq: rank by tuple[0], at here it's d[u]
    hp.heappush(path_heap, (0, init_vertex))

    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: d[u] + w[u,v]
                alt_path = distance[current] + cost
                if alt_path < distance[adj]:
                    # update path_list
                    distance[adj] = alt_path
                    # update heap
                    hp.heappush(path_heap, (alt_path, adj))
                    color[adj] = GRAY
                    parents[adj] = current

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices = int(_input[0])
    v_info = map(lambda x: x.split(), _input[1:])
    # assert len(init_vertices_table) == vertices_num

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

    adj_table = generate_adj_table(v_info)
    ans = dijkstra_path_heap()
    for i, v in enumerate(ans):
        print(i, v)

Submission status: Accepted

Solution code:
import heapq
N=int(input())
ad_li=[[]for i in range(N)]
for i in range(N):
    nums=list(map(int,input().split()))
    f=nums[0]
    for j in range(nums[1]):
        t=nums[j*2+2]
        c=nums[j*2+3]
        ad_li[f].append([t,c])

memo=[1E18 for i in range(N)]
memo[0]=0
qu=[]
heapq.heappush(qu,(0,0))
while len(qu)!=0:
    atop=heapq.heappop(qu)
    for ne in ad_li[atop[1]]:
        next_cost=atop[0]+ne[1]
        if(memo[ne[0]]>next_cost):
            memo[ne[0]]=next_cost
            heapq.heappush(qu,(next_cost,ne[0]))
for i in range(N):
    print(i,memo[i])