Problem:


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

Single Source Shortest Path II

  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 10,000$

$0 \leq c_i \leq 100,000$

$|E| < 500,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 heapq import*
I=float("inf")
def m():
 n=int(input())
 A=[[]]*n
 for _ in range(n):
  e=list(map(int,input().split()))
  A[e[0]]=zip(e[2::2],e[3::2])
 d=[0]+[I]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 for i in range(n):print(i,d[i])
m()

Submission status: Accepted

Solution code:
from heapq import*
I=float("inf")
def m():
 n=int(input())
 A=[]
 for _ in range(n):
  e=list(map(int,input().split()))
  A+=[zip(e[2::2],e[3::2])]
 d=[0]+[I]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 for i in range(n):print(i,d[i])
m()

Submission status: Accepted

Solution code:
from heapq import*
I=float("inf")
def m():
 n=int(input())
 A=[]
 for _ in range(n):
  e=list(map(int,input().split()))
  A+=[zip(e[2::2],e[3::2])]
 d=[0]+[I]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print('\n'.join(f'{i} {d[i]}'for i in range(n)))
m()

Submission status: Accepted

Solution code:
import sys
from heapq import*
e=sys.stdin.readline
I=float("inf")
def m():
 n=int(e())
 A=[]
 for _ in[0]*n:
  b=list(map(int,e().split()))
  A+=[zip(b[2::2],b[3::2])]
 d=[0]+[I]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print('\n'.join(f'{i} {d[i]}'for i in range(n)))
m()

Submission status: Accepted

Solution code:
from heapq import*
I=float("inf")
def m():
 n=int(input())
 A=[]
 for _ in[0]*n:
  e=list(map(int,input().split()))
  A+=[zip(e[2::2],e[3::2])]
 d=[0]+[I]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print('\n'.join(f'{i} {d[i]}'for i in range(n)))
m()

Submission status: Accepted

Solution code:
from heapq import*
def m():
 n=int(input())
 A=[]
 for _ in[0]*n:
  e=list(map(int,input().split()))
  A+=[zip(e[2::2],e[3::2])]
 d=[0]+[float("inf")]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print('\n'.join(f'{i} {d[i]}'for i in range(n)))
m()

Submission status: Accepted

Solution code:
import sys
from heapq import*
def m():
 n=int(input())
 A=[]
 for e in sys.stdin:
  e=list(map(int,e.split()))
  A+=[zip(e[2::2],e[3::2])]
 d=[0]+[float('inf')]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print('\n'.join(f'{i} {d[i]}'for i in range(n)))
m()

Submission status: Accepted

Solution code:
from heapq import*
def m():
 n=int(input())
 A=[]
 for _ in[0]*n:
  e=list(map(int,input().split()))
  A+=[zip(e[2::2],e[3::2])]
 d=[0]+[float('inf')]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print('\n'.join(f'{i} {d[i]}'for i in range(n)))
m()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappop, heappush
def inpl(): return list(map(int, input().split()))
INF = float("inf")
N = int(input())
G = []
for _ in range(N):
    I = inpl()
    G.append(zip(*[I[3::2], I[2::2]]))

def dijkstra(G):
    C = [INF]*(N)
    C[0] = 0
    visited = [False] * (N)
    Q = [[0, 0]]

    while Q:
        c, u = heappop(Q)
        if C[u] < c:
            continue
        visited[u] = True
        for d, v in G[u]:
            if visited[v]:
                continue
            e = c + d
            if e < C[v]:
                C[v] = e
                heappush(Q, [e, v])
    return C

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

Submission status: Accepted

Solution code:
from heapq import *
h = []




INF = 1e9

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


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

    heappush(h, (d[s], s))

    while h:
        pop = heappop(h)
        if pop[0] == INF:
            continue
        for node in a[pop[1]]:
            if d[pop[1]] + node[1] < d[node[0]]:
                d[node[0]] = d[pop[1]] + node[1]
                heappush(h, (d[pop[1]] + node[1], node[0]))

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

Submission status: Accepted

Solution code:
N = int(input())
G = [[] for i in range(N)]
for nod in range(N):
    U = list(map(int, input().split()))[2:]
    G[nod] = zip(U[0::2], U[1::2])



import heapq


def dijkstra(x):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


distance = dijkstra(0)
#print(distance)
for i in range(N):
    print(i, distance[i])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from enum import Enum, auto

INFTY = float('inf')

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

n = int(input())
adj_list = []
for i in range(n):
    u, k, *kv = list(map(int, input().split(' ')))
    adj_list.append(kv)

colors = []
d = []

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

    heappush(pque, (0, s))

    while len(pque) >= 1:
        vert_u = heappop(pque)
        u = vert_u[1]
        colors[u] = Color.BLACK
        if d[u] < vert_u[0]: continue
        i = 0
        while i <= len(adj_list[u])-2:
            v = adj_list[u][i]
            if colors[v] != Color.BLACK:
                if d[u] + adj_list[u][i+1] < d[v]:
                    d[v] = d[u] + adj_list[u][i+1]
                    colors[v] = Color.GRAY
                    heappush(pque, (d[v], v))
            i += 2

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

Submission status: Accepted

Solution code:
from queue import PriorityQueue
 
INF=1<<30
n=int(input())
adj=[[]for i in range(n+1)]
maxx = 10010

def dijkstra():
    global adj
    PQ=PriorityQueue()
      
    d=[INF for i in range(n)]
    #p=[-1 for i in range(n)]
    flag=[0 for i in range(n)]
 
    d[0] = 0;
    PQ.put((0, 0))
    while (not PQ.empty()):
        f = PQ.get()
        u = f[1]
        
        # 标记已经加入S
        flag[u] = 1

        #如果不是最小最短路径则忽略
        #if (d[u] >f[0] ):
            #continue
        lens = len(adj[u])
        for j in range(lens):
            v = adj[u][j][0]
            if (flag[v] == 0 and d[v] > d[u] + adj[u][j][1]):
                d[v] = d[u] + adj[u][j][1]
                PQ.put((d[v], v));
            

    for i in range(n):
        if d[i]==INF:
            print("%d %d"%(i, -1))
        else:
            print("%d %d"%(i, d[i]))
        

for i in range(n):
    s=[int(x) for x in input().split()]
    u=s[0]
    k=s[1]
    for j in range(k):
        adj[u].append((s[j*2+2],s[2*j+3]))
 
dijkstra()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys


class SSSP:
    """Given weighted graph, find Single Sorce Shortest Path from node 0.

    >>> st = SSSP([[(2, 3), (3, 1), (1, 2)], \
                   [(0, 2), (3, 4)], \
                   [(0, 3), (3, 1), (4, 1)], \
                   [(2, 1), (0, 1), (1, 4), (4, 3)], \
                   [(2, 1), (3, 3)]])
    >>> [st.weight(n) for n in range(5)]
    [0, 2, 2, 1, 3]
    """
    def __init__(self, graph):
        self.size = len(graph)
        self.tree = []
        self.weights = [-1] * self.size
        self._search(graph)

    def weight(self, n):
        return self.weights[n]

    def _search(self, graph):
        h = []
        self.weights[0] = 0
        count = 1
        for i, w in graph[0]:
            heappush(h, (w, 0, i))

        while count < self.size:
            while len(h) > 0:
                weight, src, dst = heappop(h)
                if self.weights[dst] < 0:
                    self.weights[dst] = weight
                    count += 1
                    self.tree.append((src, dst))
                    for i, w in graph[dst]:
                        if self.weights[i] < 0:
                            heappush(h, (w+weight, dst, i))
                    break


def run():
    n = int(input())

    nodes = [None] * n
    for line in sys.stdin:
        id_, deg, *edges = [int(i) for i in line.split()]
        nodes[id_] = []
        for _ in range(deg):
            tgt, wgt, *edges = edges
            nodes[id_].append((tgt, wgt))

    st = SSSP(nodes)
    for node in range(n):
        print('{} {}'.format(node, st.weight(node)))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
import queue


class Edge:
    def __init__(self, from_v, to_v, cost):
        self.from_v = from_v
        self.to_v = to_v
        self.cost = cost

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

    def get_from_v(self):
        return self.from_v

    def get_to_v(self):
        return self.to_v

    def get_cost(self):
        return self.cost


class Vertex:
    def __init__(self, cost, id):
        self.cost = cost
        self.id = id

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

    def get_cost(self):
        return self.cost

    def get_id(self):
        return self.id


class Dijkstra:
    def __init__(self, number_of_vertex):
        # self.edges = []
        self.graf = [[] for _ in range(number_of_vertex)]
        self.number_of_vertex = number_of_vertex
        self.distance = []  # 最短距離
        self.INF = 1145141919810

    def add_edge(self, from_v, to_v, cost):
        # self.edges.append(Edge(from_v, to_v, cost))
        self.graf[from_v].append(Edge(from_v, to_v, cost))

    def compute_shortest_distance(self, start):
        self.distance = [self.INF] * self.number_of_vertex
        self.distance[start] = 0
        que = queue.PriorityQueue()

        que.put(Vertex(0, start))

        while not que.empty():
            top = que.get()
            cost = top.get_cost()
            id = top.get_id()
            if self.distance[id] < cost: continue
            for a_edge in self.graf[id]:
                to_v = a_edge.get_to_v()
                from_v = a_edge.get_from_v()
                prev_cost = self.distance[from_v]
                next_cost = self.distance[to_v]
                if next_cost > prev_cost + a_edge.get_cost():
                    next_cost = prev_cost + a_edge.get_cost()
                    self.distance[to_v] = next_cost
                    que.put(Vertex(next_cost, to_v))


n = int(input())
dij = Dijkstra(n)

for i in range(n):
    tmp = list(map(int, input().split()))
    u = tmp[0]
    k = tmp[1]
    vc = tmp[2:]
    for j in range(k):
        dij.add_edge(u, vc[2 * j], vc[2 * j + 1])

dij.compute_shortest_distance(0)

for i in range(n):
    print(str(i) + " " + str(dij.distance[i]))

Submission status: Accepted

Solution code:
# coding: utf-8

import heapq


class Dijkstra:

    """
    Dijkstra's algorithm: find the shortest path from a vertex
    O(E + log(V))
    verified:
        https://onlinejudge.u-aizu.ac.jp/#/courses/lesson/1/ALDS1/12/ALDS1_12_B
    """

    def __init__(self, V, G, INF=float("inf")):

        """
        V: the number of vertexes
        E: adjacency list (all edge in G must be 0 or positive)
        INF: Infinity distance
        """
        self.V = V
        self.G = G
        self.INF = INF
        self.distance, self.prev = list(), list()


    def dijkstra(self, start):

        Q = list()
        self.distance = [self.INF for _ in range(self.V)]
        self.prev = [-1 for _ in range(self.V)]

        self.distance[start] = 0
        heapq.heappush(Q, (0, start))

        while len(Q) > 0:
            dist, from_v = heapq.heappop(Q)
            if self.distance[from_v] < dist:
                continue
            for to_v, nxt_dist in self.G[from_v]:
                if self.distance[from_v] + nxt_dist >= self.distance[to_v]:
                    continue
                self.distance[to_v] = self.distance[from_v] + nxt_dist
                heapq.heappush(Q, (self.distance[to_v], to_v))
                self.prev[to_v] = from_v
        
        return self.distance


    def get_path(self, goal):

        path = [goal]
        while self.prev[goal] != -1:
            path.append(prev[goal])
            goal = self.prev[end]

        return path[::-1]


if __name__ == "__main__":
    
    """
    an example of use
    """

    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n):
        v, _, *e = map(int, input().split())
        for u, d in zip(e[::2], e[1::2]):
            g[v].append((u, d))
 

    dist = Dijkstra(n, g).dijkstra(0)
    for i, d in enumerate(dist):
        print(i, d)

Submission status: Accepted

Solution code:
import heapq

n = int(input())

INF = 2147483647
G = [[] for i in range(n)]
check, dist = [0 for i in range(n)], [INF for i in range(n)]


def dijkstra(s):
    dist[s], pq = 0, []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)
        check[u[1]] = 2

        if dist[u[1]] < u[0]:
            continue

        for v in G[u[1]]:
            if check[v[0]] != 2:
                if dist[u[1]] + v[1] < dist[v[0]]:
                    dist[v[0]], check[v[0]] = dist[u[1]] + v[1], 1
                    heapq.heappush(pq, (dist[v[0]], v[0]))


def main():
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(data[1]):
            G[data[0]].append((data[2*(j+1)], data[2*(j+1)+1]))

    dijkstra(0)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

class Dijkstra:
    """
        Dijkstra's algorithm: find the shortest paths from a vertex
        complexity:
            O(E + logV)
    """
    def __init__(self, V, E, start, INF=10**9):
        """
        :param V: the number of vertices
        :param E: adjacency list (all edge in E must be non negative)
        :param start: start vertex
        :param INF: Infinity distance
        """
        self.V = V
        self.E = E
        self.dijkstra(start, INF)

    def dijkstra(self, start, INF):
        que = list()
        self.distance = [INF] * self.V
        self.prev = [-1] * self.V
        self.distance[start] = 0
        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 get_path(self, end):
        path = [end]
        while self.prev[end] != -1:
            end = self.prev[end]
            path.append(end)
            return path[::-1]


V = int(input())
edges = [[] for _ in range(V)]
for _ in range(V):
    u, _, *e = map(int, input().split())
    for t, d in zip(e[::2], e[1::2]):
        edges[u].append((t, d))

djk = Dijkstra(V, edges, 0)
for i, d in enumerate(djk.distance):
    print(i, d)

Submission status: Accepted

Solution code:
import sys
    
def shortest_path(GRAPH, distance):
    
    nodes0 = range(len(distance))
    nodes1 = set()
    p1 = 0
    distance[p1] = 0
    while True:
        dp1 = distance[p1]
        gp1 = GRAPH[p1]
        status[p1]=2
        for p2 in gp1.keys():
            tmp = gp1[p2] + dp1
            if status[p2]<=1 and tmp < distance[p2]:
                distance[p2] = tmp
                status[p2] = 1
                nodes1.add(p2)

        p1 = -1
        mini = 1000000
            
        for p2 in nodes1:
            if distance[p2]<mini:
                p1 = p2
                mini = distance[p2]
        if mini == 1000000:
            break
        nodes1.remove(p1)
    return

def resultout(distance):
    for i in xrange(len(distance)):
        print "%d %d" %(i, distance[i])
    return

n = int(raw_input())
x = [{} for i in xrange(n)]
status = [0 for i in xrange(n)]
distance = [1000000 for i in xrange(n)]

for i in xrange(n):
    seq = map(int, raw_input().split())
    tmp={}
    for j in xrange(2, len(seq), 2):
        j2, weight = seq[j:j+2]
        tmp[j2] = weight
    x[seq[0]] = tmp
    status[i] = 0

shortest_path(x, distance)
resultout(distance)

Submission status: Accepted

Solution code:
import sys
    
def shortest_path(GRAPH, distance):
    
    nodes = set()
    p1 = 0
    distance[p1] = 0

    while True:
        dp1 = distance[p1]
        gp1 = GRAPH[p1]
        status[p1]=1
        for p2 in gp1.keys():
            tmp = gp1[p2] + dp1
            if status[p2]==0 and tmp < distance[p2]:
                distance[p2] = tmp
                nodes.add(p2)

        p1 = -1
        mini = 1000000
            
        for p2 in nodes:
            if distance[p2]<mini:
                p1 = p2
                mini = distance[p2]
        if mini == 1000000:
            break
        nodes.remove(p1)
    return

def resultout(distance):
    for i in xrange(len(distance)):
        print "%d %d" %(i, distance[i])
    return

n = int(raw_input())
x = [{} for i in xrange(n)]
status = [0 for i in xrange(n)]
distance = [1000000 for i in xrange(n)]

for i in xrange(n):
    seq = map(int, raw_input().split())
    tmp={}
    for j in xrange(2, len(seq), 2):
        j2, weight = seq[j:j+2]
        tmp[j2] = weight
    x[seq[0]] = tmp
    status[i] = 0

shortest_path(x, distance)
resultout(distance)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def main():
    num = int(stdin.readline())

    edges = []
    for _ in xrange(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in xrange(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxint] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxint and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from collections import defaultdict


class Dijkstra:
    """Graph input:
    {
    node:{node:cost,node:cost...},
    node:{node:cost,node:cost...},
    ...
    }
    """

    def __init__(self, graph: dict, N: int):
        self.graph = graph
        self.costs = [float("inf")] * N

    def calculate(self, start):
        queue = list()

        # step1: push the start point into the priority queue
        self.costs[start] = 0
        heappush(queue, (0, start))  # (cost,node)

        while queue:
            # step2: get the minimum cost node from unfixed node and fix the cost
            cost_from_start, min_node = heappop(queue)

            # step3: update the direct connected nodes
            for link, cost in self.graph[min_node].items():
                if cost_from_start + cost < self.costs[link]:
                    self.costs[link] = cost_from_start + cost
                    heappush(queue, (self.costs[link], link))

        return self.costs


n = int(input())
graph = defaultdict(dict)

for _ in range(n):
    data = [int(i) for i in input().split()]
    u = data[0]
    count = data[1]
    for j in range(1, count + 1):
        v = data[2 * j]
        w = data[2 * j + 1]
        graph[u][v] = w

dijkstra = Dijkstra(graph, n)
costs = dijkstra.calculate(0)

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

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()

    # (距離, 接する頂点)の情報を持つ有向グラフのデータを生成
    graph = [[] for _ in range(N)]
    for _ in range(N):
        v1, k, *vertices = il()
        for idx in range(0, k * 2, 2):
            v2, c = vertices[idx:idx + 2]
            graph[v1].append((c, v2))

    # ダイクストラ法
    dist = [INF] * N    # 各頂点までの距離を保持する配列
    dist[0] = 0         # 開始始点の頂点は距離をゼロとする
    visited = [0] * N   # 各頂点の訪問状態を保持する配列[0: 未訪問, 1: 訪問済み]
    heap = [(0, 0)]     # 距離と始点頂点（自分自身への移動距離はゼロ）
    heapq.heapify(heap) # 距離と頂点の情報を距離で優先度付きキューとする
    while heap:
        # 頂点uとuに到達するまでの距離
        min_cost, u = heapq.heappop(heap)

        # さらに小さい距離で既に到達済みの場合はcontinue
        if dist[u] < min_cost: continue
        visited[u] = 1  # 頂点uを訪問済みにする

        # グラフの情報から接する頂点と移動距離を順に処理
        for cost, v in graph[u]:
            if visited[v] != 1:
                if dist[u] + cost < dist[v]:
                    # 未到達かつ小さい距離で移動できる場合には
                    # 距離の更新と優先度付きキューに(距離, 頂点)の情報を追加
                    dist[v] = dist[u] + cost
                    heapq.heappush(heap, (dist[v], v))
    # 回答
    for n in range(N):
        print(n, dist[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
import heapq

infty = 2**21

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

    d[0] = 0
    PQ = [(0, 0)]
    heapq.heapify(PQ)
    color[0] = 1

    while PQ:
        f = heapq.heappop(PQ)
        u = f[1]
        color[u] = 2

        #最小値を取り出し、それが最短でなければ無視
        if d[u] < f[0]:
            continue

        for adj_u in adj[u]:
            v = adj_u[0]
            if color[v] == 2:
                continue
            if d[v] > d[u] + adj_u[1]:
                d[v] = d[u] + adj_u[1]
                heapq.heappush(PQ, (d[v], v))
                color[v] = 1


    for i in range(n):
        print(str(i) + ' ' + str(-1 if d[i] == infty else d[i]))


n = int(input())

adj = [0]*n

for _ in range(n):
    u, k, *vc = map(int, input().split())
    vx_tuple = [0] * k
    for i, (v, c) in enumerate(zip(vc[::2], vc[1::2])):
        #pythonにはvectorないので、tupleで代用
        vx_tuple[i] = (v, c)
    adj[u] = vx_tuple


dijkstra(n)

Submission status: Accepted

Solution code:
import queue

def dijkstra(s):
    color = ["white"]*n
    d = [float('inf')]*n
    d[s] = 0
    
    pq = queue.PriorityQueue()
    
    pq.put((0,s))
    
    while not pq.empty():
        u = pq.get()
        color[u[1]] = "black"
        
        if d[u[1]] < u[0]:
            continue
            
        for v,w in zip(Adj[u[1]][2::2],Adj[u[1]][3::2]):
            if color[v] != "black":
                if d[u[1]] + w < d[v]:
                    d[v] = d[u[1]]+w
                    color[v] = "gray"
                    pq.put((d[v],v))
                    
    return d

n = int(input())
Adj = [list(map(int,input().split())) for _ in range(n)]
ans = dijkstra(0)

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

Submission status: Accepted

Solution code:
import heapq
n=int(input())
p=[-1 for i in range(n)]
inf=100000000
d=[inf for i in range(n)]
M=[[] for i in range(n)]
color=["white" for i in range(n)]
Q=[]
heapq.heapify(Q)

for i in range(n):
    tmp=list(map(int,input().split()))
    root=tmp[0]
    k=tmp[1]
    for j in range(k):
        M[root].append((tmp[2*(j+1)+1],tmp[2*(j+1)]))

def dijkstra(s):
    d[s]=0
    heapq.heappush(Q,(d[s],s))
    color[s]="gray"
    while Q:
        f=heapq.heappop(Q)

        u=f[1]
        color[u]="Black"
        if f[0]>d[u]:
            continue
        for i in range(len(M[u])):
            if color[M[u][i][1]]!="Black":
                v=M[u][i][1]
                if d[v]>d[u]+M[u][i][0]:
                    d[v]=d[u]+M[u][i][0]
                    color[M[u][i][1]]="gray"
                    heapq.heappush(Q,(d[M[u][i][1]],M[u][i][1]))
                    
dijkstra(0)

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

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


class Edge:
    def __init__(self,arg_to,arg_dist):
        self.to = arg_to
        self.dist = arg_dist

class Info:
    def __init__(self,arg_node_id,arg_sum_dist):
        self.node_id = arg_node_id
        self.sum_dist = arg_sum_dist

    def __lt__(self,another):
        return self.sum_dist < another.sum_dist


V = int(input())
G = [[] for _ in range(V)] #隣接グラフ
min_dist = [BIG_NUM]*V

for _ in range(V):
    node_id,num_adj,*tmp_array = list(map(int,input().split()))
    for i in range(0,len(tmp_array),2):
        G[node_id].append(Edge(tmp_array[i],tmp_array[i+1]))

min_dist[0] = 0
Q = []
heappush(Q, Info(0,0))

while len(Q) > 0:
    info = heappop(Q)
    if info.sum_dist > min_dist[info.node_id]:continue
    for e in G[info.node_id]:
        if min_dist[e.to] > info.sum_dist+e.dist:
            min_dist[e.to] = info.sum_dist+e.dist
            heappush(Q, Info(e.to,min_dist[e.to]))

for i in range(V):
    print("%d %d"%(i,min_dist[i]))

Submission status: Accepted

Solution code:
from heapq import *
n = int(input())
INF = float("inf")
adj = [[] for _ in range(10**4+4)]
for _ in range(n):
    a,*b = map(int,input().split())
    if b[0] != 0:
        c = b[1:]
        for i in range(len(c)//2):
            k,w = c[2*i],c[2*i+1]
            adj[a].append((k,w))
H = []
heapify(H)
searched = [0]*n
d = [INF]*n
d[0] = 0
heappush(H, (0,0))
while H:
    f = heappop(H)
    u = f[-1]
    searched[u] = 1
    if d[u] < f[0]:
        continue
    for j in range(len(adj[u])):
        v = adj[u][j][0]
        if searched[v]:
            continue
        if d[v] > d[u]+adj[u][j][-1]:
            d[v] = d[u]+adj[u][j][-1]
            heappush(H,(d[v],v))
for i in range(n):
    ans = -1 if d[i] == INF else d[i]
    print(i,ans)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
A = [[]for i in range(N)]

for i in range(N):
    u, k, *nums = list(map(int,input().split()))
    for j in range(k):
        t = nums[j*2]
        c = nums[j*2+1]
        A[u].append([t, c])

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

Submission status: Accepted

Solution code:
import sys, collections, heapq
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def dijkstra(G, s):
    que = []
    d = [INF]*len(G)
    d[s] = 0
    heapq.heappush(que, (d[s], s))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for e in G[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(que, (d[e[0]], e[0]))
    return d

def resolve():
    n = I()
    G = [[] for _ in range(n)]
    for i in range(n):
        ukvc = LI()
        u = ukvc[0]
        k = ukvc[1]
        for j in range(k):
            v = ukvc[2*j+2]
            c = ukvc[2*j+3]
            G[u].append((v, c))

    ans = dijkstra(G, 0)
    for i, e in enumerate(ans):
        print(i, e)

if __name__ == '__main__':
    resolve()