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:
from enum import Enum


class Sssp(object):
    """ single source shortest path """
    INFINITY = 999999999
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  # ????¨????
        gray = 2  # ?¨???????
        black = 3  #?¨???????

    def __init__(self, data):
        num_of_nodes = len(data)
        self.color = [Sssp.Status.white] * num_of_nodes  # ????????????????¨??????¶???
        self.M = [[Sssp.INFINITY] * num_of_nodes for _ in range(num_of_nodes)]
        self._make_matrix(data)  # data????????????????????£??\??????(?????\?¶???¨???????????????????????§????????????)
        self.d = [Sssp.INFINITY] * num_of_nodes
        self.p = [-1] * num_of_nodes  # ????????????????????????????¨??????????

    def _make_matrix(self, data):
        for d in data:
            my_id = d[0]
            d = d[2:]
            while len(d) > 1:
                to_node, cost = d[0], d[1]
                self.M[my_id][to_node] = cost
                d = d[2:]

    def dijkstra(self, start):
        self.d[start] = 0
        self.p[start] = -1

        while True:
            mincost = Sssp.INFINITY
            for i in range(len(self.d)):
                if self.color[i] != Sssp.Status.black and self.d[i] < mincost:
                    mincost = self.d[i]
                    u = i

            if mincost == Sssp.INFINITY:
                break

            self.color[u] = Sssp.Status.black

            for v in range(len(self.d)):
                if self.color[v] != Sssp.Status.black and self.M[u][v] != Sssp.INFINITY:
                    if self.d[u] + self.M[u][v] < self.d[v]:
                        self.d[v] = self.d[u] + self.M[u][v]
                        self.p[v] = u
                        self.color[v] = Sssp.Status.gray


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    data = []
    for i in range(num):
        data.append(list(map(int, input().split(' '))))

    # ???????????¢?´¢
    s = Sssp(data)
    s.dijkstra(0)

    # ???????????¨???
    for i in range(num):
        print('{0} {1}'.format(i, s.d[i]))

Submission status: Accepted

Solution code:
#coding:utf-8
def Dijkestra(G,n):
    d=[100000000000]*n
    pi=[None]*n
    d[0]=0
    C=[]
    for i in range(n):
        C.append(i)
    
    while len(C)!=0:
        u=C[0]
        for i in range(1,len(C)):
            if d[u]>d[C[i]]:
                u=C[i]
        C.remove(u)
        for i in range(len(G[u])):
            if G[u][i]==-1:
                continue
            elif d[i]>d[u]+G[u][i]:
                d[i]=d[u]+G[u][i]
                pi[i]=u                
    for i in range(n):
        print(i,d[i])
    

if __name__=="__main__":
    n=int(input())
    G=[]
    for i in range(n):
        a=[]
        ele=list(map(int,input().split()))
        k=ele[1]
        t=ele[2:]
        v=c=[]
        for j in range(k):
            v=v+[t[2*j]]
            c=c+[t[2*j+1]]
        for j in range(n):
            if j in v:
                a.append(c[v.index(j)])
            else:
                a.append(-1)
        G.append(a)
    Dijkestra(G,n)

Submission status: Accepted

Solution code:
import sys
inf = float('inf')

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def SSSP(n, Adj):
    d = [inf] * n
    p = [-1] * n
    checked = [False] * n
    d[0] = 0
    checked[0] = True
    u = 0

    for i in range(n - 1):
        for v, cost in Adj[u]:
            if d[u] + cost < d[v]:
                p[v] = u
                d[v] = d[u] + cost

        min_n = 0
        min_w = inf
        for v in range(n):
            if not checked[v] and d[v] < min_w:
                min_n = v
                min_w = d[v]

        u = min_n
        checked[u] = True

    return d

def solve():
    n = int(input())
    Adj = [[] for i in range(n)]

    for i in range(n):
        u, k, *line = [int(i) for i in input().split()]
        for j in range(k):
            Adj[u].append((line[2*j], line[2*j + 1]))

    # debug(Adj, locals())

    d = SSSP(n, Adj)

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
INF = float('inf')


def dijkstra(source):
    distance[source] = 0
    parent[source] = -1

    while True:
        mincost = INF
        for i in range(n):
            if color[i] != 'black' and distance[i] < mincost:
                mincost = distance[i]
                u = i

        if mincost == INF:
            break

        color[u] = 'black'

        for v in range(n):
            if color[v] != 'black' and adjMat[u][v] != INF:
                if distance[u] + adjMat[u][v] < distance[v]:
                    distance[v] = distance[u] + adjMat[u][v]
                    parent[v] = u
                    color[v] = 'gray'


n = int(input())
color = ['white'] * n
parent = [-1] * n
distance = [INF] * n

adjMat = [[INF] * n for _ in range(n)]
for i in range(n):
    inputList = list(map(int, input().split()))
    adjRow = inputList[0::2][1:]
    weightRow = inputList[1::2][1:]
    for v, weight in zip(adjRow, weightRow):
        adjMat[i][v] = weight

dijkstra(0)

for index, distance in enumerate(distance):
    print(('{} {}').format(index, distance))

Submission status: Accepted

Solution code:
"""Shortest Path"""

import sys
import os
import pprint

#fd = os.open('ALDS1_12_B.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

level = True
def debug(v):
    if level:
        print(v)

n = int(input())
INF = float('inf')
W = [[INF for j in range(n)] for i in range(n)]

for _ in range(n):
    l = list(map(int, input().split()))
    node_index = l[0]
    num = l[1]
    data = l[2:]
    for i in range(num):
        node = data[i*2]
        weight = data[i*2+1]
        W[node_index][node] = weight

d = [INF] * n
visited = [False] * n
parent = [None] * n

# root
d[0] = 0

while True:
    min_dist = INF
    min_index = None
    for i in range(n):
        if not visited[i] and d[i] < min_dist:
            min_dist = d[i]
            min_index = i

    if min_index is None:
        break

    # accept
    visited[min_index] = True

    for i in range(n):
        if not visited[i] and d[i] > d[min_index] + W[min_index][i]:
            d[i] = d[min_index] + W[min_index][i]
            parent[i] = min_index
for i in range(len(d)):
    s = '{} {}'.format(i, d[i])
    print(s)

Submission status: Accepted

Solution code:
import heapq

def dijkstra(G, s):
    n = len(G)
    INF = float("inf")
    d = [INF] * n
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s)) # (cost, vertex)
    while pq:
        c, v = heapq.heappop(pq)
        if d[v] < c:
            continue
        for nv, nc in G[v]:
            if d[nv] > d[v] + nc:
                d[nv] = d[v] + nc
                heapq.heappush(pq, (d[nv], nv))
    return d

n = input()
G = [[] for i in xrange(n)]
for i in xrange(n):
    li = map(int, raw_input().split())
    for j in xrange(li[1]):
        G[i].append((li[2 * (j + 1)], li[2 * (j + 1) + 1]))

d = dijkstra(G, 0)
for i, c in enumerate(d):
    print i, c

Submission status: Accepted

Solution code:
inf = float("inf")
n = int(input())
M = [[inf for i in range(n)] for i in range(n)]
for i in range(n):
    L = list(map(int, input().split()))
    for j in range(L[1]):
        M[L[0]][L[2 * j + 2]] = L[2 * j + 3]


def dijkstra(s):
    color = [0] * n
    d = [inf] * n
    d[s] = 0

    while True:
        mincost = inf
        for i in range(n):
            if color[i] !=1 and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == inf: break
        color[u] = 1
        for v in range(n):
            if color[v] != 1 and M[u][v] != inf:
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]

    return d

d = dijkstra(0)
for i,v in enumerate(d):
 print("{} {}".format(i,v))

Submission status: Accepted

Solution code:
INF = 1000000


def diikstraMethd(G, s):
    # ?????????
    n = len(G)
    # White:0 Gyay:1 Black:2
    color = [0 for _ in range(n)]
    d = [INF for _ in range(n)]
    p = [None for _ in range(n)]

    d[s] = 0

    while True:
        mincost = INF
        for i in range(n):
            if color[i] != 2 and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == INF: break

        color[u] = 2

        for v in range(n):
            if color[v] != 2 and M[u][v] != INF:
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    color[u] = 1

    return d


if __name__ == '__main__':
    n = int(input())
    M = [[INF for _ in range(n)] for i in range(n)]
    for _ in range(n):
        tmp = list(map(int, input().split()))
        u = tmp.pop(0)
        k = tmp.pop(0)
        for _ in range(k):
            v = tmp.pop(0)
            c = tmp.pop(0)
            M[u][v] = c
    d = diikstraMethd(M, 0)

    for i in range(n):
        print('{0} {1}'.format(i, d[i]))

Submission status: Accepted

Solution code:
from sys import stdin
INF = 1<<21
WHITE, GRAY, BLACK = 0, 1, 2
n = int(stdin.readline())
M = [[INF] * n for _ in range(n)]
for u in range(0, n):
    U = list(map(int, stdin.readline().split()[2:]))
    for j in range(0, len(U), 2):
        M[u][U[j]] = U[j + 1]
d = [INF] * n
d[0] = 0
color = [WHITE] * n
color[0] = GRAY
def dijkstra():
    global n
    while True:
        minv = INF
        u = -1
        for i in range(0, 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(0, n):
            if color[v] != BLACK and M[u][v] != INF and d[v] > d[u] + M[u][v]:
                d[v] = d[u] + M[u][v]
                color[v] = GRAY
    for i in range(0, n):
        print(i, (-1 if d[i] == INF else d[i]))
dijkstra()

Submission status: Accepted

Solution code:
n = int(raw_input())

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

for i in range(n):
    line = raw_input()
    splited = line.split()
    splited = map(lambda x: int(x), splited)
    u = splited[0]
    k = splited[1]
    for j in range(k):
        matrix[u][splited[2 + j * 2]] = splited[2 + j * 2 + 1]

cost = [10000000000 for i in range(n)]
selected = []
now_node = 0
cost[now_node] = 0
while len(selected) != n + 1:
    selected.append(now_node)

    for (i, item) in enumerate(matrix[now_node]):
        if item < 100001 and cost[i] > item + cost[now_node] and cost[i] != -1:
            cost[i] = item + cost[now_node]
    now_node = -1
    for (i, item) in enumerate(cost):
        if i not in selected and now_node == -1:
            now_node = i
        elif i not in selected and item < cost[now_node]:
            now_node = i

for (i, item) in enumerate(cost):
    print i, item

Submission status: Accepted

Solution code:
from collections import defaultdict

def dijkstra(G, s):
  heap = Heap()
  heap.push((s, 0))
  fixed = set()
  d = defaultdict(lambda: 999999999999999999999)
  d[s] = 0
  while len(heap.data) > 0:
    v = heap.pop()
    if v in fixed:
      continue
    for u in G[v]:
      if u in fixed:
        continue
      c = G[v][u]
      if d[v] + c < d[u]:
        d[u] = d[v] + c
        heap.push((u, d[u]))
    fixed.add(v)
  return d


class Heap:
  def __init__(self):
    self.data = []

  def push(self,x):
    self.data.append(x)
    i = len(self.data)-1
    while self._p(i) >= 0:
      if self.data[i][1] < self.data[self._p(i)][1]:
        tmp = self.data[i]
        self.data[i] = self.data[self._p(i)]
        self.data[self._p(i)] = tmp
        i = self._p(i)
      else:
        break

  def pop(self):
    ret = self.top()
    n = self.data.pop()
    if len(self.data) > 0:
      self.data[0] = n
      i = 0
      while True:
        if self._l(i) < len(self.data):
          l = self.data[self._l(i)]
        else:
          l = (-1, 999999999999999999999)
        if self._r(i) < len(self.data):
          r = self.data[self._r(i)]
        else:
          r = (-1, 999999999999999999999)
        if l[1] > r[1]:
          if r[1] < self.data[i][1]:
            tmp = self.data[i]
            self.data[i] = self.data[self._r(i)]
            self.data[self._r(i)] = tmp
            i = self._r(i)
          else:
            break
        else:
          if l[1] < self.data[i][1]:
            tmp = self.data[i]
            self.data[i] = self.data[self._l(i)]
            self.data[self._l(i)] = tmp
            i = self._l(i)
          else:
            break
    return ret[0]

  def top(self):
    return self.data[0]

  def _p(self, i):
    i = i+1
    return i//2-1

  def _l(self, i):
    i = i+1
    return i*2-1

  def _r(self, i):
    i = i+1
    return i*2


G = {}

n = int(input())
for _ in range(n):
  entry = [int(v) for v in input().strip().split(' ')]
  u = entry[0]
  k = entry[1]
  G[u] = {}
  for i in range(k):
    v = entry[2+i*2]
    c = entry[3+i*2]
    G[u][v] = c

d = dijkstra(G, 0)

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

Submission status: Accepted

Solution code:
INF = 1e9

n = int(input())
adj_matrix = [[INF for i in range(n)] for j in range(n)]

for i in range(n):
    u, k, *line = list(map(int, input().split()))
    for j in range(k):
        adj_matrix[u][line[2*j]] = line[2*j+1]

def dijkstra(x):
    isVisited = [False] * x
    d = [INF] * x 
    d[0] = 0
    p = [0] * x 
    
    while True:
        min_cost = INF
        
        for i in range(x):
            if isVisited[i] != True and d[i] < min_cost:
                min_cost = d[i]
                u = i
        
        if min_cost == INF:
            break
        
        isVisited[u] = True
        
        for v in range(x):
            if isVisited[v] != True and adj_matrix[u][v] != INF:
                if d[u] + adj_matrix[u][v] < d[v]:
                    d[v] = d[u] + adj_matrix[u][v]
                    p[v] = u
    return d

for i, di in enumerate(dijkstra(n)):
    print(i, di)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())
INF = float("inf")
adj = [[INF]*N for _ in range(N)]

for n in range(N):
    inp = tuple(map(int, input().split()))
    assert n == inp[0]
    for i in range(inp[1]):
        adj[inp[0]][inp[2*i+2]] = inp[2*i+3]

not_MST = list(range(1, N))
MST = [0]
costs = {n:INF for n in range(N)}
costs[0] = 0

for n in range(1, N):
    if adj[0][n] < INF:
        costs[n] = adj[0][n]

m = 0

while len(not_MST):
    tmp_min = INF
    tmp_idx = -1
    
    for n in not_MST:
        if costs[m] + adj[m][n] < costs[n]:
            costs[n] = costs[m] + adj[m][n]
    
    for m in not_MST:
        if costs[m] < tmp_min:
            tmp_min = costs[m]
            tmp_idx = m
    
    MST.append(tmp_idx)
    not_MST.remove(tmp_idx)
    m = tmp_idx

for n in range(N):
    print("{} {}".format(n, costs[n]))

Submission status: Accepted

Solution code:
n = int(raw_input())
a = [[10**9 for i in range(n)] for j in range(n)]
for i in range(n):
    data = map(int, raw_input().split())
    a[data[0]][data[0]] = 0
    for j in range(data[1]):
        a[data[0]][data[j*2+2]] = data[j*2+3]
ans = [[10**9 for i in range(n)] for j in range(n+1)]
ans[0][:] = a[0][:]
for j in range(1, n+1):
    for k in range(n):
        for l in range(n):
            if ans[j][k] > ans[j-1][l] + a[l][k]:
                ans[j][k] = ans[j-1][l] + a[l][k]
        if ans[j][k] == 10**9:    
            ans[j][k] = ans[j-1][k]
for i in range(n):
    print i, ans[-1][i]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop

N = int(input())
INF = float("inf")
adj = []
for _ in range(N):
    inp = tuple(map(int, input().split()))
    adj.append(tuple(zip(inp[2::2], inp[3::2])))

checked = [False for _ in range(N)]
d = [float("inf") for _ in range(N)]
d[0] = 0

heap = [[0, 0]] # cost, vec

while heap:
    c, u = heappop(heap)
    if d[u] < c or checked[u]:
        continue
    for nu, nc in adj[u]:
        new_d = d[u] + nc
        if new_d < d[nu]:
            d[nu] = new_d
            heappush(heap, [d[nu], nu])
    checked[u] = True

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

Submission status: Accepted

Solution code:
n = int(input())
from collections import defaultdict
G = defaultdict(list)
for i in range(n):
    i = [int(i) for i in input().split()]
    k = i[1]
    G[i[0]] = list(zip(i[2::2],i[3::2]))

def mind(Q, d):
    c = float('inf')
    ret = 0
    for i, j in enumerate(d):
        if c > j and i in Q:
            c = j
            ret = i
    return ret

def dijkstra(G):
    d = [0] + [float('inf')] * (n - 1)
    Q = set(range(n))
    while len(Q) != 0:
        u = mind(Q, d)
        Q = Q - set([u])
        for v, c in G[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
    return d

for i,j in enumerate(dijkstra(G)):
    print(i, j)

Submission status: Accepted

Solution code:
def dijkstra():
    N = input()
    M = [ [float('inf')] * N for i in xrange(N)]
    color = [0] * N
    d = [float('inf')] * N
    p = [-1] * N

    d[0] = 0
    p[0] = -1

    for i in xrange(N):
        l = map(int, raw_input().split())

        for j in xrange(l[1]):
            M[i][l[2 * (j+1)]] = l[2 * (j+1) + 1]

    while 1:
        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] != float('inf'):
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    color[v] = 1

    for i in xrange(N):
        if d[i] == float('inf'):
            d[i] = -1
        print i,d[i]

if __name__ == '__main__':
    dijkstra()

Submission status: Accepted

Solution code:
def main():
    n = input()
    inf = float('inf')
    M = [[inf]*n for i in xrange(n)]
    for i in xrange(n):
        Ai = map(int,raw_input().split())
        for j in xrange(Ai[1]):
            M[i][Ai[2+2*j]] = Ai[3+2*j]

    d = dijkstra(0,M,n)
    for i in xrange(n):
        print i, d[i]

def dijkstra(s,M,n):
    inf = float('inf')
    c = [-1]*n
    d = [inf]*n
    p = [-1]*n
    d[s] = 0

    while(True):
        mincost = inf
        for i in xrange(n):
            if (c[i] != 1) & (d[i] < mincost):
                mincost = d[i]
                u = i
        if mincost == inf:
            break

        c[u] = 1

        for v in xrange(n):
            if (c[v] != 1) & (M[u][v] != inf):
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    c[v] = 0
    return d

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

n = int(input())
d = [float("inf") for i in range(n)]
d[0] = 0
g = []
q = []

for i in range(n):
    heapq.heappush(q, (d[i], i))
    inp = list(map(int, input().split()))
    tmp = []
    for j in range(inp[1]):
        tmp.append(inp[2*j+2:2*j+4])
    g.append(tmp)

while q:
    q_pop = heapq.heappop(q)
    i = q_pop[1]
    if q_pop[0] > 100*100000:
        continue
    for node in g[i]:
        d_tmp = d[i] + node[1]
        if d_tmp < d[node[0]]:
            d[node[0]] = d_tmp
            heapq.heappush(q, (d_tmp, node[0]))

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

Submission status: Accepted

Solution code:
n = int(input())
edgeList = []
rootList = [-1 for i in range(n)]
parent = [-1 for i in range(n)]
lenList = [0 for i in range(n)]
sumLength = 0
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(a[1]):
        edgeList.append([a[2*j+3], i, a[2*j+2]])


rootList = [-1 for i in range(n)]
parent = [0 for i in range(n)]
lenList = [float("inf") for i in range(n)]
lenList[0] = 0
def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]

flag = True
while flag:
    flag = False
    edgeList.sort(key=lambda x: (x[0] + lenList[x[1]]))
    for e in edgeList:    # weight:e[0], e[1]->e[2]
        if e[2] == 0:
            continue
        x = getRoot(e[1])
        y = getRoot(e[2])
        if x == 0 != y:
            parent[e[2]] = e[1]
            lenList[e[2]] = lenList[e[1]] + e[0]
            rootList[y] = 0
            flag = True
            break

for i, j in zip(range(n), lenList):
    print(i, j)

Submission status: Accepted

Solution code:
from sys import stdin

INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2

n = int(stdin.readline())
M = [[INFTY for i in range(n)] for j in range(n)]

for u in range(n):
    U = list(map(int, stdin.readline().split()[2:]))
    for j in range(0, len(U), 2):
        M[u][U[j]] = U[j+1]

d = [INFTY for i in range(n)]
color = [WHITE for i in range(n)]

def dijkstra():
    global n
    d[0] = 0
    color[0] = GRAY
    while(1):
        minv = INFTY
        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] != INFTY):
                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, (-1 if d[i] == INFTY else d[i]))
dijkstra()

Submission status: Accepted

Solution code:
n = int(input())
edgeList = []
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(a[1]):
        edgeList.append([a[2*j+3], i, a[2*j+2]])
 
 
rootList = [-1 for i in range(n)]
parent = [0 for i in range(n)]
lenList = [float("inf") for i in range(n)]
lenList[0] = 0
def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
 
flag = True
while flag:
    flag = False
    edgeList.sort(key=lambda x: (x[0] + lenList[x[1]]))
    for e in edgeList:    # weight:e[0], e[1]->e[2]
        if e[2] == 0:
            continue
        x = getRoot(e[1])
        y = getRoot(e[2])
        if x == 0 != y:
            parent[e[2]] = e[1]
            lenList[e[2]] = lenList[e[1]] + e[0]
            rootList[y] = 0
            flag = True
            break
 
for i, j in zip(range(n), lenList):
    print(i, j)

Submission status: Accepted

Solution code:
inf = float('inf')
n = int(input())
g = []
for i in range(n):
    line = list(map(int, input().split()))
    k = line[1]
    c = [inf] * n
    for j in range(k):
        v = line[2 + 2 * j]
        c[v] = line[3 + 2 * j]
    g.append(c)

distance = [inf] * n
distance[0] = 0
visited = [False] * n
current = 0

while not all(visited):
    visited[current] = True
    min_i = 0
    min_d = inf
    for i in range(n):
        if not visited[i]:
            if distance[current] + g[current][i] < distance[i]:
                distance[i] = distance[current] + g[current][i]
            if distance[i] < min_d:
                min_i = i
                min_d = distance[i]
    current = min_i

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import heapq
q = [] # プライオリティキュー


n = int(input())
V = dict()
d = dict()

for i in range(n):
    data = list(map(int, input().split()))
    V[data[0]] = data[2:]
    d[data[0]] = float('inf')

d[0] = 0
heapq.heappush(q, (0, 0)) #(d[id], id)
S = set()

while len(S) != len(V):
    dist, node_id = heapq.heappop(q)
    S.add(node_id)
    for u, c in zip(V[node_id][0::2], V[node_id][1::2]): #隣接ノード
        if c + d[node_id] < d[u]:
            d[u] = c + d[node_id]
            heapq.heappush(q, (d[u], u))
            #print("Update:", u, d[u])
for i in range(n):
    print(i, d[i])

Submission status: Accepted

Solution code:
from heapq import *

#edge {to cost}
#P {mindirection, modeNum}
#G a list which contain informations of nodes

# building G from input
V=int(input())
G=[]
for _ in range(V):
    temp=list(map(int,input().split()))
    l=[]
    for i in range(1,temp[1]+1):
        l.append(temp[2*i:2*(i+1)])
    G.append(l)

que=[] #having the minimum distance
INF=1e8
d=[INF for i in range(V)] #having the distance
d[0]=0
heappush(que,[0,0])

while len(que)!=0:
    p=heappop(que)
    v=p[1]
    if(d[v]<p[0]):
        continue
    for i in range(len(G[v])):
        e=G[v][i]
        if(d[e[0]]>d[v]+e[1]):
            d[e[0]]=d[v]+e[1]
            heappush(que,[d[e[0]],e[0]])
            
for i in range(V):
    print(i,d[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


if __name__ == '__main__':

    n = int(input())
    M = [[float("inf") for j in range(n)] for i in range(n)]

    for i in range(n):
        l = list(map(int, input().split(" ")))
        for k in range(l[1]):
            j = l[2 + 2 * k]
            c = l[2 + 2 * k + 1]
            M[i][j] = c

    d = [float("inf")] * n

    def dijkstra(s):
        color = [0] * n
        p = [None] * n
        d[s] = 0
        p[s] = -1

        while True:
            mincost = float("inf")
            for i in range(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 range(n):
                if color[v] != 2:
                    if d[u] + M[u][v] < d[v]:
                        d[v] = d[u] + M[u][v]
                        p[v] = u
                        color[v] = 1

    dijkstra(0)
    for i in range(n):
        print(i, d[i])

Submission status: Accepted

Solution code:
from collections import deque
INF = float("inf")
def MAIN():
    n = int(input())
    G = [[i, INF] for i in range(n)]
    G[0][1] = 0
    m = {}
    for _ in range(n):
        A = list(map(int, input().split()))
        m[A[0]] = {}
        for i in range(2, len(A), 2):
            m[A[0]][A[i]] = A[i + 1]
    dp = deque([0])
    while dp:
        u = dp.popleft()
        for v, c in m[u].items():
            if G[v][1] > G[u][1] + c:
                G[v][1] = G[u][1] + c
                dp.append(v)
    print("\n".join(" ".join(map(str, a)) for a in G))
MAIN()

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
INF = float("inf")
def MAIN():
    n = int(input())
    G = [[i, INF] for i in range(n)]
    G[0][1] = 0
    m = {}
    for _ in range(n):
        A = list(map(int, input().split()))
        m[A[0]] = {}
        for i in range(2, len(A), 2):
            m[A[0]][A[i]] = A[i + 1]
    dp = [(0, 0)]
    while dp:
        cost, u = heappop(dp)
        for v, c in m[u].items():
            if G[v][1] > G[u][1] + c:
                G[v][1] = G[u][1] + c
                heappush(dp, (G[v][1], v))
    print("\n".join(" ".join(map(str, a)) for a in G))
MAIN()

Submission status: Accepted

Solution code:
n=int(input())
M=[[-1]*n for _ in[0]*n]
for _ in[0]*n:
 e=list(map(int,input().split()))
 for i in range(e[1]):k=2*-~i;M[e[0]][e[k]]=e[k+1]
d=[0]+[1e6]*~-n
c=[1]*n
while 1:
 m,u=1e6,-1
 for i in range(n):
  if m>d[i]and c[i]:m,u=d[i],i
 if u<0:break
 c[u]=0
 for v in range(n):
  if c[v]and 1+M[u][v]and d[v]>d[u]+M[u][v]:
   d[v]=d[u]+M[u][v]
for i in range(n):print(i,d[i])

Submission status: Accepted

Solution code:
n=int(input())
M=[[-1]*n for _ in[0]*n]
for _ in[0]*n:
 e=list(map(int,input().split()))
 for i in range(e[1]):k=2*-~i;M[e[0]][e[k]]=e[k+1]
d=[0]+[1e6]*n
c=[1]*n
while 1:
 m,u=1e6,-1
 for i in range(n):
  if m>d[i]and c[i]:m,u=d[i],i
 if u<0:break
 c[u]=0
 for v in range(n):
  if c[v]and 1+M[u][v]and d[v]>d[u]+M[u][v]:
   d[v]=d[u]+M[u][v]
for i in range(n):print(i,d[i])

Submission status: Accepted

Solution code:
INF = 1e9

n = int(input())
a = [[-1 for i in range(n)]for i in range(n)]
for i in range(n):
    b = list(map(int, input().split()))
    index = b[0]
    k = b[1]
    for j in range(k):
        a[index][b[2+j*2]] = b[3+j*2]


def dijkstra(s):
    flag = [0] * n
    d = [INF] * n
    d[s] = 0
    p = [-1] * n

    while True:
        min_cost = INF

        for i in range(n):
            if flag[i] != 1 and d[i] < min_cost:
                min_cost = d[i]
                u = i
        if min_cost == INF:
            break
        flag[u] = 1

        for v in range(n):
            if flag[v] != 1 and a[u][v] != -1:
                if a[u][v] + d[u] < d[v]:
                    d[v] = d[u] + a[u][v]
                    p[v] = u
    return d
d = dijkstra(0)
for i in range(n):
    print(i, d[i])

Submission status: Accepted

Solution code:
from enum import Enum, auto

INFTY = float('inf')

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

n = int(input())
M = [[-1 for i in range(n)] for i in range(n)]
for i in range(n):
    line = list(map(int, input().split(' ')))
    if line[1] == 0: continue
    for j in range(2, 2+2*line[1], 2):
        M[i][line[j]] = line[j+1]


colors = []
d = []
p = [-1 for i in range(n)]

def dijkstra(s):
    global d
    colors = [Color.WHITE for i in range(n)]
    d = [INFTY for i in range(n)]
    d[s] = 0
    p[s] = -1

    while True:
        mincost = INFTY
        for i in range(n):
            if colors[i] != Color.BLACK and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == INFTY: break
        colors[u] = Color.BLACK

        for v in range(n):
            if colors[v] != Color.BLACK and M[u][v] != -1:
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    colors[v] = Color.GRAY

dijkstra(0)
for i in range(n):
    print(i, d[i])