Problem:


Single Source Shortest Path

  For a given weighted graph G(V, E) and a source r, find the source shortest path to each vertex from the source (SSSP: Single Source Shortest Path).

Input

An edge-weighted graph G (V, E) and the source r.

|V| |E| r
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1

|V| is the number of vertices and |E| is the number of edges in G. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the source of the graph.

si and ti  represent source and target vertices of i-th edge (directed) and di represents the cost of the i-th edge.

Output

Print the costs of SSSP in the following format.

c0
c1
:
c|V|-1

The output consists of |V| lines. Print the cost of the shortest path from the source r to each vertex 0, 1, ... |V|-1 in order. If there is no path from the source to a vertex, print INF. 

Constraints

 1 ≤ |V| ≤ 100000

0 ≤ di ≤ 10000

 0 ≤ |E| ≤ 500000

 There are no parallel edges

 There are no self-loops

Sample Input 1

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

Sample Output 1

0
1
3
4

Sample Input 2

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

Sample Output 2

3
0
2
INF



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


Sample output:
0
1
3
4

Submission status: Accepted

Solution code:
#https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A
import math
import heapq
V,E,r=map(int,input().split())
edge=[[] for _ in range(V)]     # edge[i] : 頂点iからの辺、edge[i][j]:[v,c] 頂点iから頂点vまでの辺、コストc
d=[math.inf for _ in range(V)]  #頂点sからの最短距離

for i in range(E):
    si,ti,di=map(int,input().split())
    edge[si].append([ti,di])
#    edge[ti].append([si,di]) #有向なのでここは無し

#優先度付きキュー
q=[]
heapq.heapify(q)

def dijkstra(start):
    d[start]=0 #初期値
    heapq.heappush(q, [0,start])

    while(len(q)!=0):
        #まだ使われてない頂点のうち距離が最小のものを探す。ない場合は終了
        di=heapq.heappop(q)
        distance=di[0]
        v=di[1]

        if(d[v] < distance):
            continue

        ei = edge[v]
        for i in range(len(ei)):
            e = ei[i]
            if(d[e[0]] > d[v]+e[1]):
                d[e[0]] = d[v]+e[1]
                heapq.heappush(q, [d[e[0]],e[0]])

dijkstra(r)
for i in range(len(d)):
    print(d[i] if d[i]!=math.inf else "INF")

Submission status: Accepted

Solution code:
import heapq
class Graph:
    #def __init__(self, N, adj):
    def __init__(self, N):
        self.number_of_node = N
        self.neighbour_list = [[] for _ in range (N)]
        #self.adj = adj

    def connect(self, from_node, to_node, weight):
        """
        from_nodeからto_nodeに長さweightの辺を追加する
        """
        self.neighbour_list[from_node].append((to_node, weight))
        #self.adj[from_node][to_node] = weight

    def dijkstra(self, source_node, target_node = None):
        """
        source_nodeからtarget_nodeへの最短路計算
        source_nodeの入次数は0と仮定する
        """
        INF = -1
        dist = [INF] * self.number_of_node
        #prev = [-1] * self.number_of_node
        dist[source_node] = 0
        hq = []
        heapq.heappush(hq, (0, source_node))
        while len(hq) > 0:
            d, from_node = heapq.heappop(hq)
            if dist[from_node] < d:
                continue
            #for to_node in range(self.number_of_node):
            for to_node, weight in self.neighbour_list[from_node]:
                """
                weight = adj[from_node][to_node]
                # 辺がないところはスキップ
                if weight < 0:
                    continue
                """
                if dist[to_node] == INF or dist[from_node] + weight < dist[to_node]:
                    dist[to_node] = dist[from_node] + weight
                    heapq.heappush(hq, (dist[to_node], to_node))
                    #prev[to_node] = from_node
        if target_node is None:
            return dist
        else:
            return dist[target_node]

V, E, r = map(int, input().strip().split())
graph = Graph(V)
#adj = [[-1 for _ in range(V)] for _ in range(V)]
for i in range(E):
    s, t, d = map(int, input().strip().split())
    graph.connect(s,t,d)
    #adj[s][t] = d
#graph = Graph(V, adj)
dist = graph.dijkstra(r)
for d in dist:
    if d == -1:
        print("INF")
    else:
        print(d)

Submission status: Accepted

Solution code:
#配列アクセスを減らした
#入力変更
#出力変更
#tupleで済むところをlistから変更
#変数名以外2907313と同一に見える
import heapq
v, e, r = map(int, input().split( ))
E = [[] for _ in range(v)]
inf = 10**10
for _ in range(e):
    s,t,d = map(int, input().split( ))
    E[s].append((t,d))
D = [inf for _ in range(v)]
#Prev = [-1 for _ in range(v)]
D[r] = 0
Q = []
heapq.heappush(Q, (0,r))
#print(E)
#popからheappopに変更
while Q:
    d,q = heapq.heappop(Q) #qは[距離、頂点番号]：キューの優先度の都合で番号が後
    #print(q)
    for n,c in E[q]:#nは[辺の終点、辺の長さ]
        if D[n]>d+c:
            D[n] = d+c
            #Prev[n] = q
            heapq.heappush(Q, (d+c,n))

for d in D:
    if d<inf:
        print(d)
    else:
        print("INF")

Submission status: Accepted

Solution code:
V,E,Start = map(int,input().split())
INF = 10**20
Edge = []
D = [INF]*V
for _ in range(E):
    Edge.append(list(map(int,input().split())))

D[Start] = 0
while True:
    update = False
    for i in range(E):
        fr   = Edge[i][0]
        to   = Edge[i][1]
        cost = Edge[i][2]

        if D[fr] != INF and D[to] > D[fr] + cost:
            D[to] = D[fr] + cost
            update = True
    if update == False:
        break
for d in D:
    if d == INF:
        print('INF')
    else:
        print(d)

Submission status: Accepted

Solution code:
N, M, S = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    s, t, d = map(int, input().split())
    G[s].append([t, d])


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0
    visited = [False] * n

    # 距離・頂点
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        visited[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (visited[to]) or (distances[to] <= new_dist):
                continue

            distances[to] = new_dist
            heapq.heappush(hq, (new_dist, to))

    return distances


ans = dijkstra(G, S)
for a in ans:
    print(a if a != float('inf') else 'INF')

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import heapq
import os
import sys


def main():
    V, E, R = read_ints()
    G = [dict() for _ in range(V)]
    for _ in range(E):
        s, t, d = read_ints()
        G[s][t] = d
    print(*solve(V, E, R, G), sep='\n')


def solve(V, E, R, G):
    dists = [-1] * V
    q = []
    heapq.heappush(q, (0, R))
    while q:
        d, i = heapq.heappop(q)
        if dists[i] != -1:
            continue
        dists[i] = d
        for j, e in G[i].items():
            if dists[j] == -1:
                heapq.heappush(q, (d + e, j))
    return ['INF' if d == -1 else d for d in dists]


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
def dijkstra(g, s):
    '''現時点で最短のものをheapqにぶち込みながら探索していく．
    '''
    n = len(g)
    dist = [10**9] * n
    dist[s] = 0
    hq = []
    heapq.heappush(hq, (dist[s], s))
    while hq:
        cost, u = heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v, c in g[u]:
            if dist[v] <= dist[u] + c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq, (dist[v], v))
    return dist

v, e, r = map(int, input().split())
g = [[] for _ in range(v)]
for i in range(e):
    s, t, c = map(int, input().split())
    g[s].append((t, c))
if e == 0:
    for i in range(v):
        if i == r:
            print(i)
        else:
            print("INF")
else:
    rets = dijkstra(g, r)
    for item in range(v):
        if rets[item] == 10**9:
            print("INF")
        else:
            print(rets[item])

Submission status: Accepted

Solution code:
import heapq
INF = float('inf')


def dijkstra(g, s):
    n = len(g)
    dist = [INF] * n
    dist[s] = 0
    hq = []
    heapq.heappush(hq, (dist[s], s))
    while hq:
        cost, u = heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v, c in g[u]:
            if dist[v] <= dist[u] + c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq, (dist[v], v))
    return dist


V, E, r = map(int, input().split())
g = [[] for _ in range(V)]
for _ in range(E):
    s, t, d = map(int, input().split())
    g[s].append((t, d))
ds = dijkstra(g, r)
for d in ds:
    print('INF' if d == INF else d)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = 10**10
a,b,c = map(int,input().split())
d = [[] for i in range(a)]
for i in range(b):
    ta,tb,tc = map(int,input().split())
    d[ta].append((tb,tc))

def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    for i in range(a):
        print(dist[i] if dist[i] < INF else "INF")
dijkstra(a,d,c)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys

INF = sys.maxsize

v_num, e_num, src = map(int, input().split())
graph = [[] for _ in range(v_num)]

for _ in range(e_num):
  s, t, dist = map(int, input().split())
  graph[s].append((t, dist))

heap = []
dst = [INF for _ in range(v_num)]

heappush(heap, (0, src))
dst[src] = 0

while heap:
  dist, node = heappop(heap)
  for to, cost in graph[node]:
    if dst[to] > cost + dist:
      dst[to] = cost + dist
      heappush(heap, (cost + dist, to))

for dist in dst:
  if dist == INF:
    print("INF")
  else:
    print(dist)

Submission status: Accepted

Solution code:
import heapq
INF = 100000000000000

def make_adj_list(v):
    adj_list = []
    for i in range(v):
        adj_list.append([])
    return adj_list

def dijkstra(v, e, adj_list, s):
    heap = []
    d = []
    pre = []
    for i in range(v):
        d.append(INF)
        pre.append(s)
    d[s] = 0
    heapq.heappush(heap, (0, s))
    while len(heap) != 0:
        candidate_d, now_v = heapq.heappop(heap)
        if d[now_v] < candidate_d:
            continue
        for v, cost in adj_list[now_v]:
            if d[v] > d[now_v] + cost:
                d[v] = d[now_v] + cost
                heapq.heappush(heap,(d[v], v))
                pre[v] = now_v
    return d, pre

def main():
    v, e, s = map(int, input().split())
    adj_list = make_adj_list(v)
    for i in range(e):
        a = [int(i) for i in input().split()]
        adj_list[a[0]].append((a[1], a[2]))
        
    d, pre = dijkstra(v, e, adj_list, s)

    for i in range(v):
        if d[i] == INF:
            print("INF")
        else:
            print(d[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

def main():
    [V, E, r] = [int(num) for num in input().split()]

    edges = {}
    for i in range(V):
        edges[i] = []
    for i in range(E):
        num_list = [int(num) for num in input().split()]
        edges[num_list[0]].append((num_list[1], num_list[2]))

    dist = [10**10 for _ in range(V)]

    dist[r] = 0

    PQ = []

    heapq.heappush(PQ, (0, r))
    # for i, val in enumerate(dist):
    #     heapq.heappush(PQ, (val, i))

    while len(PQ) > 0:
        (_, node_num) = heapq.heappop(PQ)

        for edge in edges[node_num]:
            # print(edge)
            new_len = dist[node_num] + edge[1]

            if new_len < dist[edge[0]]:
                heapq.heappush(PQ, (new_len, edge[0]))
                dist[edge[0]] = new_len

    for i in range(V):
        if dist[i] == 10**10:
            print('INF')
        else:
            print(dist[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
V,E,r = map(int, input().split())
Graph = [[] for _ in range(V)] 
for _ in range(E):
        s,t,d = map(int, input().split())
        Graph[s].append((t,d)) 
pq = []
dist = [10**10]*V
dist[r] = 0
heapq.heappush(pq, (0, r))
while pq:
        w, n = heapq.heappop(pq)
        for node, weight in Graph[n]:
                newlen = w + weight
                if newlen < dist[node]:
                        dist[node] = newlen
                        heapq.heappush(pq, (dist[node], node))
for i in dist:
        if i == 10**10:
                print("INF")
        else:
                print(i)

Submission status: Accepted

Solution code:
def main():
	V,E,r,*L = map(int,open(0).read().split())
	INF = float("inf")
	G = [[] for _ in range(V)]
	for s,t,c in zip(*[iter(L)]*3):
		G[s].append((t,c))
	for i in dijkstra(G,r):
		if i==INF:
			print("INF")
		else:
			print(i)

from heapq import heappop,heappush
def dijkstra(G:list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF]*V
	D[source] = 0
	vis = [False]*V
	H = [(0,source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D

if __name__=="__main__":main()

Submission status: Accepted

Solution code:

class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self,V=False):
        self.adj={}
        self.nodes={}
        
        if V>0:
            for v in range(0,V):
                self.nodes[v]={}
                self.adj[v]={}



    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # グラフのノード数
        #dist = [float('inf') for i in range(N)] # 始点から各頂点までの最短距離を格納する
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        #print(self.nodes)
        if N==0:
            return dist
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        #vtx=list(self.nodes)
        #vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist

    def prim(self):

        import heapq

        nodes=list(self.nodes.keys())
        N=len(nodes)

        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(self.adj[X[0]][u],X[0],u))

        total_cost=0
        used={n:False for n in nodes}
        used[X[0]]=True
        while True:
            #print(unused)
            #print(X,total_cost)
            cost,u,v=heapq.heappop(unused)
            if used[v]:
                continue
            X.append(v)
            used[v]=True
            total_cost+=cost
            if len(X)==N:
                break

            for u in self.adj[v]:
                if used[u]:
                    continue
                heapq.heappush(unused,(self.adj[u][v],v,u))

        return total_cost




    def show(self):

        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()

        for u in self.adj:
            for v in self.adj[u]:

                #G.add_edge(e.node_from,e.node_to,weight=e.cost)
                G.add_edge(u,v,weight=self.adj[u][v])
                #print(e.node_from,e.node_to,e.cost)

        pos=nx.spring_layout(G)
        #nx.draw_networkx_edges(G,pos=pos,edgelist=G.edges())
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])

        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        #nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        #plt.axis('off')
        #nx.draw(G,with_labels=True)
        plt.show()



def acinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    V,E,r=acinput()

    g=myGraph(V)


    for i in range(E):
        ss=acinput()
        #g.add_edge((ss[0],ss[1]),ss[2])
        g.add_directed_edge((ss[0],ss[1]),ss[2])

    #print(g.adj)
    #print(g.show())
    #print(g.prim())
    dist=g.dijkstra(r)
    #print(sorted(dist))
    #dist=sorted(dist.items(),key=lambda x:x[0])
    dist=sorted(dist.items())
    #print(dist)
    for node,val in dist:
        #tmp=dist[sd]
        if val==float('inf'):
            val="INF"
        print(val)

    #g.show()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
from typing import List, Tuple


if __name__ == "__main__":
    V, E, r = map(lambda x: int(x), input().split())

    edges: List[List[Tuple[int, int]]] = [[] for _ in range(V)]
    dists = [sys.maxsize for _ in range(V)]
    dists[r] = 0

    for _ in range(E):
        s, t, dist = map(lambda x: int(x), input().split())
        edges[s].append((t, dist))

    que: List[Tuple[int, int]] = []  # (dist, vertex)
    heappush(que, (0, r))

    while que:
        dist, vertex = heappop(que)
        for to, cost in edges[vertex]:
            if cost + dist < dists[to]:
                dists[to] = cost + dist
                heappush(que, (cost + dist, to))

    for dist in dists:
        if sys.maxsize == dist:
            print("INF")
        else:
            print(dist)

Submission status: Accepted

Solution code:
class RadixHeap:
    __slots__ = ["data", "last", "siz", "used"]

    # (max_key - min_key) <= C
    def __init__(self, N, C):
        self.data = [[] for i in range(C.bit_length() + 1)]
        self.last = self.siz = 0
        self.used = [0]*N

    def push(self, x, key):
        #assert self.last <= x
        self.siz += 1
        self.data[(x ^ self.last).bit_length()].append((x, key))

    def pop(self):
        data = self.data
        used = self.used
        #assert self.siz > 0
        if not data[0]:
            i = 1
            while not data[i]:
                i += 1
            d = data[i]
            new_last, new_key = min(d)
            used[new_key] = 1
            for val in d:
                x, key = val
                if used[key]:
                    self.siz -= 1
                    continue
                data[(x ^ new_last).bit_length()].append(val)
            self.last = new_last
            data[i] = []
        else:
            new_last, new_key = data[0].pop()
            used[new_key] = 1
            self.siz -= 1
        return new_last, new_key

    def __len__(self):
        return self.siz

import sys
readline = sys.stdin.readline
write = sys.stdout.write

N, M, s = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, readline().split())
    G[a].append((b, c))

INF = 10**18
def dijkstra(N, G, s):
    que = RadixHeap(N, 10**9 + 1)

    dist = [INF]*N
    dist[s] = 0
    que.push(0, s)
    while que:
        cost, v = que.pop()
        if dist[v] < cost:
            continue
        for w, c in G[v]:
            if cost + c < dist[w]:
                dist[w] = r = cost + c
                que.push(r, w)
    return dist

dist = dijkstra(N, G, s)
for c in dist:
    write("INF\n" if c == INF else "%d\n" % c)

Submission status: Accepted

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

v, e, r = map(int, input().split())
E = defaultdict(list)
for i in range(e):
    s, t, d = map(int, input().split())
    E[s].append((t, d))

D = [float("inf")]*v
D[r] = 0

q = []
heappush(q, (r, 0))
while q:
    now, dist = heappop(q)
    if D[now] < dist:
        continue

    for nxt, w in E[now]:
        t = dist + w
        if t < D[nxt]:
            D[nxt] = t
            heappush(q, (nxt, t))

for i in range(v):
    if D[i] == float("inf"):
        print("INF")
    else:
        print(D[i])

Submission status: Accepted

Solution code:
# AOJ GRL_1_A Single Sourse Shortest Path
import heapq as hp

V, E, s = map(int, input().split())
graph = [[] for _ in range(V)]
INF = 0
for _ in range(E):
    a, b, d = map(int, input().split())
    graph[a].append((d, b)) 
    #graph[b].append((d, a)) #無向グラフならこれ使う
    INF = max(INF, d)

INF = INF*(E+1) + 1
D = [INF for _ in range(V)] # 頂点iへの最短距離がD[i]
D[s] = 0 
q = [] # しまっていく優先度付きキュー
hp.heappush(q, (0, s))

while q:
    nd, np = hp.heappop(q) # 一番距離が近いものを取ってくる
    if D[np] < nd: # 追加した後の残骸は見ない
        continue
    for d, p in graph[np]:
        if D[p] > D[np] + d: # 隣接するやつの中で今よりも近くなれるなら更新
            D[p] = D[np] + d
            hp.heappush(q, (D[p], p))

for d in D:
    if d == INF:
        print('INF')
    else:
        print(d)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


from collections import defaultdict
import heapq
from collections.abc import MutableMapping


class HeapDict(MutableMapping):
    @staticmethod
    def _parent(i):
        return (i - 1) >> 1

    @staticmethod
    def _left(i):
        return (i << 1) + 1

    @staticmethod
    def _right(i):
        return (i + 1) << 1

    def __init__(self, *args, **kw):
        self.heap = []
        self.d = {}
        self.update(*args, **kw)

    def clear(self):
        del self.heap[:]
        self.d.clear()

    def __setitem__(self, key, value):
        if key in self.d:
            self.pop(key)
        wrapper = [value, key, len(self)]
        self.d[key] = wrapper
        self.heap.append(wrapper)
        self._decrease_key(len(self.heap) - 1)

    def _min_heapify(self, i):
        l = self._left(i)
        r = self._right(i)
        n = len(self.heap)
        if l < n and self.heap[l][0] < self.heap[i][0]:
            low = l
        else:
            low = i
        if r < n and self.heap[r][0] < self.heap[low][0]:
            low = r

        if low != i:
            self._swap(i, low)
            self._min_heapify(low)

    def _decrease_key(self, i):
        while i:
            parent = self._parent(i)
            if self.heap[parent][0] < self.heap[i][0]:
                break
            self._swap(i, parent)
            i = parent

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
        self.heap[i][2] = i
        self.heap[j][2] = j

    def __delitem__(self, key):
        wrapper = self.d[key]
        while wrapper[2]:
            parentpos = self._parent(wrapper[2])
            parent = self.heap[parentpos]
            self._swap(wrapper[2], parent[2])
        self.popitem()

    def __getitem__(self, key):
        return self.d[key][0]

    def __iter__(self):
        return iter(self.d)

    def popitem(self):
        """Remove and return a (key, value) pair with the lowest value"""
        wrapper = self.heap[0]
        if len(self.heap) == 1:
            self.heap.pop()
        else:
            self.heap[0] = self.heap.pop(-1)
            self.heap[0][2] = 0
            self._min_heapify(0)
        del self.d[wrapper[1]]
        return wrapper[1], wrapper[0]

    def __len__(self):
        return len(self.d)

    def peekitem(self):
        """Retuen a (key, value) pair with the lowest value"""
        return (self.heap[0][1], self.heap[0][0])


def main():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp"""
    V, E, r = readi(3)
    G = defaultdict(list)
    cost = dict()
    for _ in range(E):
        s, t, d = readi(3)
        G[s].append(t)
        cost[(s, t)] = d

    dist = arr(V, fill_value=INF)
    dist[r] = 0
    # pq = HeapDict((v, dist[v]) for v in range(V))
    pq = [(dist[r], r)]
    while pq:
        # u, _ = pq.popitem()
        _, u = heapq.heappop(pq)
        for v in G[u]:
            new_d = dist[u] + cost[(u, v)]
            if new_d < dist[v]:
                dist[v] = new_d
                # pq[v] = new_d
                heapq.heappush(pq, (dist[v], v))

    for d in dist:
        print("INF" if d == INF else d)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
v,e,r = map(int,input().split())
E = [tuple(map(int,input().split())) for one in range(e)]
D = [10**9 for two in range(v)]
D[r] = 0
for i in range(v):
    update = 0
    for s,t,d in E:
        if D[t]>D[s]+d:
            D[t] = D[s]+d
            update +=1
    if update == 0:
        break

for j in range(v):
    print(D[j] if D[j] != 10**9 else "INF")

Submission status: Accepted

Solution code:
v,e,r = map(int,input().split())
D = [float('inf')]*v
L = []
D[r] = 0
for i in range(e):
    s,t,d = map(int,input().split())
    L.append([s,t,d])
for i in range(v-1):
    update = False
    for j in range(e):
        a,b,c = L[j][0],L[j][1],L[j][2]
        if D[b] > D[a]+c:
            D[b] = D[a]+c
            update = True
    if not update:
        break
for i in range(v):
    if D[i] == float('inf'):
        print('INF')
    else:
        print(D[i])

Submission status: Accepted

Solution code:
def main():
    v,e,r=map(int,input().split())
    ans=[float('inf') for _ in range(v)]
    E = [tuple(map(int,input().split())) for _ in range(e)]
    ans[r]=0
    for i in range(v):
        update=False
        for s,t,c in E:
            if ans[t]>ans[s]+c:
                ans[t]=ans[s]+c
                update=True
        if not update:
            break
    for i in ans:
        if i==float('inf'):
            print("INF")
        else:
            print(i)
            
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
V,E,r=map(int,input().split())
W=[tuple(map(int,input().split())) for _ in range(E)]
dis=[float('inf')]*V
dis[r]=0
for _ in range(V-1):
    update=False
    for s,t,d in W:
        if dis[t] > dis[s] + d:
            dis[t] = dis[s] + d
            update = True
    if not update: break
for i in dis:
    print(i if i!=float('inf') else 'INF')

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

from heapq import heappush, heappop
def dijkstra(g,start):
    dist = [1e18]*(len(g)) #startからの最短距離
    dist[start] = 0
    q = [(0,start)] #(そこまでの距離、点)
    pending = len(g)-1 #未確定の点の個数
    while q and pending:
        c,v = heappop(q)
        if dist[v] < c: continue
        pending -= 1
        for to, cost in g[v]:
            if dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(q, (dist[to], to))
    return dist

v,e,r = [int(i) for i in input().split()]

g = [[] for _ in range(v)]
for _ in range(e):
    a,b,c = [int(i) for i in input().split()]
    g[a].append((b, c))

for i in dijkstra(g,r):
    if i == 1e18: print("INF")
    else: print(i)