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

Solution code:
n = int(input())

adj = [[False 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

weights = [9900000] * n


def search(goal, path, weight):
    e = path[-1]
    if weight < weights[goal]:
        if e == goal:
            weights[goal] = weight
        else:
            for v, c in enumerate(adj[e]):
                if (v not in path) and (c is not False):
                    path.append(v)
                    weight += c
                    search(goal, path, weight)
                    weight -= c
                    path.pop()


for i in range(n):
    search(i, [0], 0)

for v, w in enumerate(weights):
    print(v, w)

Submission status: Time Limit Exceeded

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

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

while not all(visited):
    min_i = 0
    min_d = 100001
    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]
    visited[current] = True
    current = min_i

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

Submission status: Accepted

Solution code:
# coding: utf-8

import heapq


def dj(adjm, start):
    n = len(adjm)
    d = [float("inf")] * n
    d[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while(q):
        td, v = heapq.heappop(q)
        for k in adjm[v].keys():
            nd = td + adjm[v][k]
            if d[k] > nd:
                d[k] = nd
                heapq.heappush(q, (nd, k))
    return d


def main():
    n = int(input())
    # 隣接行列
    adjm = [{} for _ in range(n)]
    for i in range(n):
        vdata = list(map(int, input().split()))
        for j in range(vdata[1]):
            v, c = vdata[j * 2 + 2], vdata[j * 2 + 3]
            adjm[i][v] = c
    ans = dj(adjm, 0)
    for i, d in enumerate(ans):
        print(i, d)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 14 19:11:44 2018

@author: maezawa
"""
infinity = 2*10**9

n = int(input())
adj = [[] for _ in range(n)]

for j in range(n):
    ain = list(map(int, input().split()))
    u = ain[0]
    k = ain[1]
    for i in range(2,2+2*k,2):
        adj[u].append([ain[i],ain[i+1]])
    #print(*adj[u])

color = [0]*n
d = [infinity for _ in range(n)]
p = [0]*n
p[0] = -1
d[0] = 0

def dyk(s):
    cnt = 1
    cur = s
    candidates = set() # remaining nodes
    while True:
        for i, w in adj[cur]:
            if color[i] == 2:
                continue
            if d[i] > d[cur] + w:
                d[i] = d[cur] + w
                color[i] = 1
            candidates.add(i)
        min_d = infinity
        for j in candidates:
            if min_d > d[j]:
                min_node = j
                min_d = d[j]
        candidates.remove(min_node)
        p[min_node] = cur
        color[cur] = 2
        cur = min_node
        cnt += 1
        #print(cur, d)
        #print(candidates)
        if cnt == n:
            break
    return

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

Submission status: Accepted

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


def dijkstra(edges, start, *, adj_matrix=False, default_value=float('inf')):
    '''
    Returns best costs to each node from 'start' node in the given graph.
    (Single Source Shortest Path - SSSP)

    If edges only include costs and destination nodes on possible edges,
    adj_matrix should be False(default), and it is generally when this functions works much faster

    Note that costs in edges should follow the rules below
    1. The cost from a node itself should be 0,
    2. If there is no edge between nodes, the cost between them should be default_value
    3. The costs can't be negative

    # sample input when given as adjacency matrix (adj_matrix=True)
    edges = [[0, 2, 5, 4, inf, inf],           # node 0
             [2, 0, inf, 3, 6, inf],           # node 1
             [5, inf, 0, 2, inf, 6],           # node 2
             [4, 3, 2, 0, 2, inf],             # node 3
             [inf, 6, inf, 2, 0, 4],           # node 4
             [inf, inf, 6, inf, 4, 0]]         # node 5

    # sample input when given not as adjacency matrix (adj_matrix=False)
    edges = [[(1, 2), (2, 5), (3, 4)],         # node 0
             [(0, 2), (3, 3), (4, 6)],         # node 1
             [(0, 5), (3, 2), (5, 6)],         # node 2
             [(0, 4), (1, 3), (2, 2), (4, 2)], # node 3
             [(1, 6), (3, 2), (5, 4)],         # node 4
             [(2, 6), (4, 4)]]                 # node 5
    '''

    n = len(edges)

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) if adj_matrix else\
                    edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


def dijkstra_route(edges,
                   start,
                   goal,
                   *,
                   adj_matrix=False,
                   default_value=float('inf'),
                   verbose=False):
    '''
    Trys to find the best route to the 'goal' from the 'start'
    '''

    n = len(edges)

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1
    prevs = [-1 for _ in [None] * n]

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) if adj_matrix else\
                    edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))
                prevs[nxt_node] = tmp_node

    min_route = []
    prev = goal
    cnt = 0
    while prev != start:
        min_route.append(prev)
        prev = prevs[prev]

        cnt += 1
        if prev == -1 or cnt > n:
            raise NoRouteError(
                'There is no possible route in this graph \nedges: {} \nstart: {} \ngoal: {}'.
                format(edges, start, goal))

    else:
        min_route.append(prev)
    min_route = min_route[::-1]
    min_cost = costs[goal]

    if verbose:
        print('---route---')
        for node in min_route[:-1]:
            print('{} -> '.format(node), end='')
        else:
            print(min_route[-1])

        print('---distance---')
        print(min_cost)

    return costs, min_route


class NoRouteError(Exception):
    pass


if __name__ == '__main__':
    '''
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_B
    '''

    n = int(input())
    edges = [[] for i in range(n)]
    for i in range(n):
        i, k, *kedges = map(int, input().split())
        for edge in zip(kedges[::2], kedges[1::2]):
            edges[i].append(edge)

    for i, cost in enumerate(dijkstra(edges, 0)):
        print(i, cost)

Submission status: Accepted

Solution code:
import sys

def dijkstra(v_count: int, edges: list, start: int,
             *, adj_matrix: bool = False, unreachable=float("inf")) -> list:
    """ ダイクストラ法
    :param v_count: 頂点数
    :param edges: 辺のリスト(隣接リストor隣接行列)
    :param start: スタートする頂点
    :param adj_matrix: edgesに渡したリストが隣接行列ならTrue
    :param unreachable: 到達不能を表すコスト値
                        隣接行列の辺の有無の判定および返すリストの初期値に使用
    """
    from heapq import heappush, heappop

    vertices = [unreachable] * v_count
    vertices[start] = 0
    q, rem = [(0, start)], v_count - 1

    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1

        dests = (filter(lambda x: x[1] != unreachable, enumerate(edges[v]))
                 if adj_matrix else edges[v])

        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))

    return vertices

n = int(input())
edges = [[] for _ in [0]*n]
for a in (tuple(map(int, l.split())) for l in sys.stdin):
    edges[a[0]] = tuple(zip(a[2::2], a[3::2]))
vertices = dijkstra(n, edges, 0)
for i, n in enumerate(vertices):
    print(i, n)

Submission status: Accepted

Solution code:
import sys

def dijkstra(v_count: int, edges: list, start: int,
             *, adj_matrix: bool = False, unreachable=float("inf")) -> list:
    """ ダイクストラ法
    :param v_count: 頂点数
    :param edges: 辺のリスト(隣接リストor隣接行列)
    :param start: スタートする頂点
    :param adj_matrix: edgesに渡したリストが隣接行列ならTrue
    :param unreachable: 到達不能を表すコスト値
                        隣接行列の辺の有無の判定および返すリストの初期値に使用
    """
    from heapq import heappush, heappop

    vertices = [unreachable] * v_count
    vertices[start] = 0
    q, rem = [(0, start)], v_count - 1

    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1

        dests = (filter(lambda x: x[1] != unreachable, enumerate(edges[v]))
                 if adj_matrix else edges[v])

        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))

    return vertices

n = int(input())
inf = float("inf")
edges = [[inf]*n for _ in [0]*n]
for a in (tuple(map(int, l.split())) for l in sys.stdin):
    _from = a[0]
    for to, cost in zip(a[2::2], a[3::2]):
        edges[_from][to] = cost
vertices = dijkstra(n, edges, 0, adj_matrix=True)
for i, n in enumerate(vertices):
    print(i, n)

Submission status: Accepted

Solution code:
from collections import deque
import sys
import heapq
n = int(input())
V = [[int(i) for i in input().split()] for _ in range(n)]
dis = [sys.maxsize for _ in range(n)]
dis[0] = 0
h = []
for i in range(n):
    heapq.heappush(h,(dis[i],i))
while(len(h)>0):
    node = heapq.heappop(h)
    tmp = node[1]
    for i in range(V[tmp][1]):
        ind = V[tmp][2*i+2]
        cos = V[tmp][2*i+3]
        if cos + dis[tmp] < dis[ind]:
            dis[ind] = cos + dis[tmp]
            heapq.heappush(h,(dis[ind],ind))
for i,j in enumerate(dis):
    print(i,j)

Submission status: Accepted

Solution code:
import sys
import heapq
n = int(input())
V = [[int(i) for i in input().split()] for _ in range(n)]
dis = [sys.maxsize for _ in range(n)]
dis[0] = 0
h = []
for i in range(n):
    heapq.heappush(h,(dis[i],i))
while(len(h)>0):
    node = heapq.heappop(h)
    tmp = node[1]
    for i in range(V[tmp][1]):
        ind = V[tmp][2*i+2]
        cos = V[tmp][2*i+3]
        if cos + dis[tmp] < dis[ind]:
            dis[ind] = cos + dis[tmp]
            heapq.heappush(h,(dis[ind],ind))
for i,j in enumerate(dis):
    print(i,j)

Submission status: Accepted

Solution code:
#coding: utf-8

inf = 1000000000


def dijkstra(s):
    d = [inf for i in range(n)]
    color = ["white" for i in range(n)]
    p = [-1 for i in range(n)]
    d[s] = 0

    while True:
        mincost = inf
        for i in range(n):
            if color[i] != "black" and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == inf:
            break

        color[u] = "black"

        for v in range(n):
            if color[v] != "black" and mtrx[u][v] != False:
                if d[u] + mtrx[u][v] < d[v]:
                    d[v] = d[u] + mtrx[u][v]
                    p[v] = u
                    color[v] = "gray"
    return d

n = int(input())
mtrx = [[False for j in range(n)] for i in range(n)]
for i in range(n):
    data = list(map(int,input().split()))
    k = data[1]
    for num in range(k):
        mtrx[i][data[2+2*num]] = data[2+2*num+1]

d = dijkstra(0)

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

Submission status: Accepted

Solution code:

n=int(input())
graph=[[0]*n for i in range(n)]


#graph[i][j]は、頂点iから頂点jへの枝の重みを表す(0は枝なし)
for loop in range(n):
    tmp_ope=list(map(int,input().split()))
    for j in range(1,tmp_ope[1]+1):
        graph[tmp_ope[0]][tmp_ope[2*j]]=tmp_ope[2*j+1]

#S[i]＝１の時、頂点iは走査済み
S=[0]*n
#d[i]はSに含まれる点のみを使って、頂点iにたどり着くときの最短パス
d=[999999]*n
d[0]=0

for loop in range(n):
    tmp_vertex=-1

    #tmp_vertexは走査済みでない点の中で、d[i]が最小となるインデックス
    for j in range(n):
        if(S[j]==0):
            if(tmp_vertex!=-1):
                if(d[j] < d[tmp_vertex]):
                    tmp_vertex=j
            else:
                tmp_vertex=j
    
    
    S[tmp_vertex]=1

    #dを更新
    for j in range(n):
        if(graph[tmp_vertex][j]!=0 and S[j]==0):
            d[j]=min([ d[j], d[tmp_vertex] + graph[tmp_vertex][j] ])

for i in range(n):
    print(f"{i} {d[i]}")

Submission status: Accepted

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

import sys
from heapq import heappush, heappop

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

# ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点)
def dijkstra(N: int, nodes: list, src: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [float('inf')] * N
    # スタート位置
    que = [(0, src)]
    res[src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # srcからの距離, 現在のノード
        dist, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxt, cost in nodes[cur]:
            # 今回の経路のが短い時
            if res[cur] + cost < res[nxt]:
                res[nxt] = res[cur] + cost
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (res[nxt], nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N=INT()
nodes=[[] for i in range(N)]
for i in range(N):
    l=LIST()
    u=l[0]
    k=l[1]
    l=l[2:]
    for j in range(0, k*2, 2):
        nodes[u].append((l[j], l[j+1]))

ans=dijkstra(N, nodes, 0)
for i in range(N):
    print(i, ans[i])

Submission status: Accepted

Solution code:
from collections import namedtuple

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))
inf = 1e9


def bf(n, s, es):
    d = [inf for _ in range(n)]
    d[s] = 0
    while True:
        updated = False
        for e in es:
            if d[e.fr] != inf and d[e.fr] + e.cost < d[e.to]:
                updated = True
                d[e.to] = d[e.fr] + e.cost

        if not updated:
            break

    return d


n = int(input())

m = [[-1 for _ in range(n)] for _ in range(n)]
es = []
for i in range(n):
    fs = list(map(int, input().split()))
    ne = fs[1]
    for j in range(ne):
        v = fs[2+2*j]
        c = fs[2+2*j+1]
        m[i][v] = c
        es.append(Edge(i, v, c))


d = bf(n, 0, es)
for (i, di) in enumerate(d):
    print(i, di)

Submission status: Accepted

Solution code:
from collections import namedtuple

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))
inf = 1e9


def bellman_ford(n, start, edges):
    dists = [inf for _ in range(n)]
    dists[start] = 0
    while True:
        updated = False
        for e in edges:
            if dists[e.fr] != inf and dists[e.fr] + e.cost < dists[e.to]:
                updated = True
                dists[e.to] = dists[e.fr] + e.cost

        if not updated:
            break

    return dists


def dijkstra(n, costs):
    dists = [inf for _ in range(n)]
    dists[0] = 0
    determined = [False for _ in range(n)]

    while True:
        v, min_d = -1, inf
        for i in range(n):
            if determined[i]:
                continue
            if dists[i] < min_d:
                v, min_d = i, dists[i]

        if v == -1:
            break

        determined[v] = True

        for i in range(n):
            if determined[i] or costs[v][i] == -1:
                continue

            dists[i] = min(dists[i], dists[v] + costs[v][i])

    return dists


n = int(input())

m = [[-1 for _ in range(n)] for _ in range(n)]
es = []
for i in range(n):
    fs = list(map(int, input().split()))
    ne = fs[1]
    for j in range(ne):
        v = fs[2+2*j]
        c = fs[2+2*j+1]
        m[i][v] = c
        es.append(Edge(i, v, c))


# d = bellman_ford(n, 0, es)
d = dijkstra(n, m)
for (i, di) in enumerate(d):
    print(i, di)

Submission status: Accepted

Solution code:
from collections import namedtuple
import heapq

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))
inf = int(1e9)


def bellman_ford(n, start, edges):
    dists = [inf for _ in range(n)]
    dists[start] = 0
    while True:
        updated = False
        for e in edges:
            if dists[e.fr] != inf and dists[e.fr] + e.cost < dists[e.to]:
                updated = True
                dists[e.to] = dists[e.fr] + e.cost

        if not updated:
            break

    return dists


def dijkstra(n, costs):
    dists = [inf for _ in range(n)]
    dists[0] = 0

    queue = []
    for (i, d) in enumerate(dists):
        heapq.heappush(queue, (d, i))

    while len(queue) > 0:
        d, i = heapq.heappop(queue)
        if d > dists[i]:
            continue

        for v in range(n):
            if v == i or costs[i][v] == inf:
                continue

            if dists[i] + costs[i][v] < dists[v]:
                dists[v] = dists[i] + costs[i][v]
                heapq.heappush(queue, (dists[v], v))

    return dists


def warshall_floyd(n, costs):
    dists = [[costs[i][j] for j in range(n)] for i in range(n)]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])

    return dists


n = int(input())

m = [[inf if i != j else 0 for i in range(n)] for j in range(n)]
es = []
for i in range(n):
    fs = list(map(int, input().split()))
    ne = fs[1]
    for j in range(ne):
        v = fs[2+2*j]
        c = fs[2+2*j+1]
        m[i][v] = c
        es.append(Edge(i, v, c))


# d = bellman_ford(n, 0, es)
# d = dijkstra(n, m)
d = warshall_floyd(n, m)
for (i, di) in enumerate(d[0]):
    print(i, di)

Submission status: Accepted

Solution code:
n = int(input())
adjc_list = [[] for _ in range(n)]
INF = 99999999999999999999
V = [ele for ele in range(n)]
S = []
d = [INF] * n
p = [ele for ele in range(n)]

for i in range(n):
    tmp = [int(ele) for ele in input().split()]
    for j in range(1, tmp[1]*2, 2):
        v = tmp[j+1]
        w = tmp[j+2]
        adjc_list[i].append([w, v])
    adjc_list[i].sort()


def my_dijkstra_solver():
    root = 0  # given
    # 1. 初期化
    d = [INF] * n
    d[root] = 0
    VS = V

    # 2. 以下の処理を、S = Vになるまで繰り返す
    while VS:
        # 2.1. V-S の中から、 d[u] が最小である頂点 u を選択する。
        u = VS[0]
        for i in VS:
            if d[i] < d[u]:
                u = i

        S.append(u)  # 2.2. u を S に追加する.

        # 2.3. u に隣接し, かつ V-S に属するすべての頂点 v に対する以下の値を更新する
        VS.remove(u)
        for w, v in adjc_list[u]:
            if v in VS:
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    p[v] = u  # 親をどこかで使うのはわかるが一旦忘れよう

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


if __name__ == "__main__":
    my_dijkstra_solver()

Submission status: Accepted

Solution code:
import io, sys, itertools
f = sys.stdin


def take2(iterable):
    i = iter(iterable)
    while True:
        yield next(i), next(i)


n = int(f.readline())
adj =[[(v, c) for v, c in take2(map(int, f.readline().split()[2:]))] for _ in range(n)]
d = [100000 * 100 + 1] * n

d[0] = 0
def search(parent, children):
    global d
    for v, c in children:
        if d[v] > d[parent] + c:
            d[v] = d[parent] + c
            search(v, adj[v])
    
search(0, adj[0])
    
for i in range(n):
    print(i, d[i])

Submission status: Accepted

Solution code:
INFTY = 100000000000000000000000000
n = int(raw_input())
graph = {}
for i in range(n):
    entry = map(int, raw_input().split(' '))
    u = entry[0]
    k = entry[1]
    graph[u] = {}
    for j in range(k):
        v = entry[2+j*2]
        c = entry[2+j*2+1]
        graph[u][v] = c

d = {}
visited = {}
for i in range(n):
    d[i] = INFTY
    visited[i] = False
s = 0
d[s] = 0
visited[s] = True

while True:
    for i in range(n):
        if not visited[i] and i in graph[s] and d[i] > d[s] + graph[s][i]:
            d[i] = d[s] + graph[s][i]
    mincost = INFTY
    minnode = -1
    for i in range(n):
        if not visited[i] and d[i] < mincost:
            mincost = d[i]
            minnode = i
    if mincost == INFTY: break
    visited[minnode] = True
    s = minnode


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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
n = int(input())
inf = 100 * 100000

M = [[inf for i in range(n)] for j in range(n)]

for i in range(n):
    L = list(map(int, input().split()))
    u = L[0]
    k = L[1]
    v = L[2::2]
    c = L[3::2]
    for j in range(k):
        M[u][v[j]] = c[j]

S = set()
V = set(range(n))
S.add(0)
d = [inf for i in range(n)]
d[0] = 0
count = 0
while len(V - S) != 0:
    T = V - S
    nd = [inf for i in range(n)]
    for s in S:
        for m, c in enumerate(M[s]):
            if d[s] + c < nd[m] and m in T:
                nd[m] = d[s] + c

    min_nd = min(nd)
    u = nd.index(min_nd)
    S.add(u)
    d[u] = min_nd


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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
from heapq import heappop, heappush
n = int(input())
inf = 100 * 100000

M = [[] for i in range(n)]

for i in range(n):
    L = list(map(int, input().split()))
    u = L[0]
    k = L[1]
    v = L[2::2]
    c = L[3::2]
    for j in range(k):
        M[u].append((v[j], c[j]))
result = [0] * n
S = set()
V = set(range(n))
S.add(0)
d = []
for m in M[0]:
    heappush(d, (m[1], m[0]))
T = V - S

while len(T) != 0:
    c, v = heappop(d)
    while v in S:
        c, v = heappop(d)
    result[v] = c
    S.add(v)
    T.remove(v)
    for m in M[v]:
        if m[0] in T:
            heappush(d, (result[v] + m[1], m[0]))

for i, v in enumerate(result):
    print(i, v)

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sys

def parse():
  n = int(raw_input())
  A = []
  for line in sys.stdin:
    fields = line.split()
    u = int(fields.pop(0))
    k = int(fields.pop(0))
    edges = {}
    for i in range(k):
      edges[int(fields[2*i])] = int(fields[2*i + 1])
    A.append(edges)
  return A

def dijkstra(s, cost):
  V = len(cost)
  d    = [float("inf")] * V
  used = [False] * V
  d[s] = 0

  while True:
    v = -1
    for u in range(V):
      if not used[u] and (v == -1 or d[u] < d[v]):
        v = u
    if v == -1:
      break
    used[v] = True
    for u in range(V):
      if not u in cost[v]: continue
      d[u] = min(d[u], d[v] + cost[v][u])

  return d

if __name__ == "__main__":
  A = parse()
  d = dijkstra(0, A)
  for i in range(len(d)):
    print i, d[i]

Submission status: Accepted

Solution code:
n = input()

M = [[float("inf") for j in xrange(n)] for i in xrange(n)]
p = [-1 for i in xrange(n)]

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

def dijksrra(s):
    color = ["WHITE" for i in xrange(n)]
    d = [float("inf") for i in xrange(n)]

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

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

    for i in xrange(n):
        print "%d %d" % (i, d[i])


dijksrra(0)

Submission status: Accepted

Solution code:
n = input()

INFTY = 1000000
color = [0 for i in xrange(n)]
d = [INFTY for i in xrange(n)]
M = [[INFTY for i in xrange(n)] for i in xrange(n)]
p = [-1 for i in xrange(n)]

def SSSP1():
    d[0] = 0

    while True:
        cost = INFTY
        for i in xrange(n):
            if color[i] != 2 and d[i] < cost:
                cost = d[i]
                u = i
            
        if cost == INFTY:
            break
        color[u] = 2
    
        for v in xrange(n):
            if color[v] != 2 and M[u][v] != INFTY and d[u] + M[u][v] < d[v]:
                d[v] = d[u] + M[u][v]
                p[v] = u
                color[v] = 1
    
    for i in range(n):
        if d[i] != INFTY:
            print i, d[i]

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

Submission status: Accepted

Solution code:
INFTY = 100000000
n = int( raw_input() )
graph = {}
for i in range(n):
  In = map( int , raw_input().split(' ') )
  u = In[0]
  k = In[1]
  graph[u] = {}
  for j in range(k):
    v = In[2+j*2]
    c = In[2+j*2+1]
    graph[u][v] = c
 
da = {}
visited = {}
for i in range(n):
  da[i] = INFTY
  visited[i] = False
s = 0
da[s] = 0
visited[s] = True
 
while True:
  for i in range(n):
    if not visited[i] and i in graph[s] and da[i] > da[s] + graph[s][i]:
      da[i] = da[s] + graph[s][i]
  cost = INFTY
  node = -1
  for i in range(n):
    if not visited[i] and da[i] < cost:
      cost = da[i]
      node = i
  if cost == INFTY: break
  visited[node] = True
  s = node
  
for i in range(n):
  print i,da[i]

Submission status: Accepted

Solution code:
INFTY = 100000000
n = int( raw_input() )
graph = {}
for i in range(n):
  In = map( int , raw_input().split(' ') )
  u = In[0]
  k = In[1]
  graph[u] = {}
  for j in range(k):
    v = In[2+j*2]
    c = In[2+j*2+1]
    graph[u][v] = c
 
da = {}
visited = {}
for i in range(n):
  da[i] = INFTY
  visited[i] = False
s = 0
da[s] = 0
visited[s] = True
 
while True:
  for i in range(n):
    if not visited[i] and i in graph[s] and da[i] > da[s] + graph[s][i]:
      da[i] = da[s] + graph[s][i]
  cost = INFTY
  node = -1
  for i in range(n):
    if not visited[i] and da[i] < cost:
      cost = da[i]
      node = i
  if cost == INFTY: 
    break
  visited[node] = True
  s = node
  
for i in range(n):
  print i,da[i]

Submission status: Accepted

Solution code:
n = int(raw_input())
a = [0 for i in xrange(n)]
adj = [[0 for i in xrange(n)] for j in xrange(n)]
for i in xrange(n):
	a[i] = map(int,raw_input().split())
for i in xrange(n):
	for j in xrange(2, a[i][1]*2+1, 2):
		adj[a[i][0]][a[a[i][0]][j]] = a[a[i][0]][j+1]
MAX = 100000000
end = [1] * n
cost = [MAX] * n
cost[0] = 0
prev = [0] * n
start = 0
while 1:
	min = MAX
	next = -1
	end[start] = 0
	for i in xrange(n):
		if end[i]:
			if adj[start][i]:
				d = cost[start] + adj[start][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i
	start = next
	if next < 0:
		break
for i in xrange(n):
	print i, cost[i]

Submission status: Accepted

Solution code:
n = int(input())
G = [[-1 for i in range(n)] for j in range(n)]
d = [999999 for i in range(n)]
  
for i in range(n):
    v = input().split()
    for j in range(int(v[1])):
        G[int(v[0])][int(v[2+2*j])] = int(v[3+2*j])

flag = [0] * n
tn = [0]
d[0] = 0
for k in range(n):
    for i in range(n):
        if i in tn:
            for j in range(n):
                if G[i][j] != -1:
                    if d[j] > d[i] + G[i][j]:
                        d[j] = d[i] + G[i][j]
                    if j not in tn:
                        tn.append(j)
  
for i in range(n):
    print(str(i) + " " + str(d[i]))

Submission status: Accepted

Solution code:
from __future__ import division, print_function
from sys import stdin, maxint
 
 
def main():
    num = int(stdin.readline())
 
    y = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        y.append([(next(it), next(it)) for _ in xrange(next(it))])
 
    weight = [maxint] * num
    weight[0] = 0
    t = set(xrange(1, num))
    index = 0
 
    while t:
        for v, cost in y[index]:
            if v not in t:
                continue
            weight[v] = min(weight[v], cost + weight[index])
 
        index = min(t, key=lambda i: weight[i])
        t.remove(index)
 
    for i, d in enumerate(weight):
        print(i, d)
 
 
main()

Submission status: Accepted

Solution code:
def dijkstra(n):
    d = [None] * 100
    p = [None] * 100
    color = [None] * 100
    
    for i in xrange(n):
        d[i] = float('inf')
        p[i] = -1
        color[i] = 0
    
    d[0] = 0
    
    while(True):
        minv = float('inf')
        u = -1
        for i in xrange(n):
            if minv > d[i] and color[i] != 2:
                u = i
                minv = d[i]
        
        if u == -1:
            break
        
        color[u] = 2
        
        for v in xrange(n):
            if color[v] != 2 and data[u][v] != float('inf'):
                if d[v] > d[u] + data[u][v]:
                    d[v] = d[u] + data[u][v]
                    p[v] = u
                    color[v] = 1

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

n = input()
data = [None] * n
for i in xrange(n):
    data[i] = [float('inf')] * n
    line = map(int, raw_input().split())
    for j in xrange(1, line[1] + 1):
        v = line[2 * j]
        c = line[2 * j + 1]
        data[line[0]][v] = c
        
dijkstra(n)