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:
import time
import sys
start=time.clock()
def main():
    [V,E,r]=input().split(" ")
    V=int(V)
    E=int(E)
    r=int(r)
    edgeset=[]
    for i in range(E):
        [s,t,d]=input().split(" ")
        edgeset.append([int(s),int(t),int(d)])

    '''infile = open("GRL_1_A_in31.txt","r")
    data=[line.rstrip().split(' ') for line in infile]
    infile.close()
    V=int(data[0][0])
    E=int(data[0][1])
    r=int(data[0][2])
    edgeset=[[int(data[a][0]),int(data[a][1]),int(data[a][2])] for a in range(1,len(data))]'''

    
    '''read the edge information and put them to edgeset'''
    '''edgeset=binary_heap_sorting(edgeset)'''
    edgeset.sort()
    nedgeset=[[]]
    parameter=0
    for i in range(len(edgeset)):
        if(edgeset[i][0]!=parameter):
            for j in range(edgeset[i][0]-parameter):
                nedgeset.append([])
            parameter=edgeset[i][0]
            nedgeset[parameter].append(edgeset[i])
        else:
            nedgeset[parameter].append(edgeset[i])
    for i in range(V-len(nedgeset)):
        nedgeset.append([])
    edgeset=nedgeset

    setS=[]
    setV=[]
    setdist=[500000*10000+1 for i in range(V)]
    '''generate the sets for optimized vertices, unoptimized vertices, distance respectively'''

    setS.append(r)
    setV.append([r,0])
    setdist[r]=0
    '''initiating data'''

    for i in range(9999999999):
        nowvert=setS[-1]
        for j in range(len(edgeset[nowvert])):
            newdist=edgeset[nowvert][j][2]+setdist[nowvert]
            olddist=setdist[edgeset[nowvert][j][1]]
            '''calculating the new distance including the on process vertices'''
            if(newdist<olddist):
                setdist[edgeset[nowvert][j][1]]=newdist
                setV=binary_heap_add(setV,newdist,edgeset[nowvert][j][1])
            '''making comparision to determin which to stay'''
        if(setV==[[r,0]]):
            break
        setS.append(setV[1][0])
        setV=binary_heap_deletion(setV)
        '''find the next on process vertice'''
                    
    for i in range(V):
        if(setdist[i]==500000*10000+1):
            print('INF')
        else:
            print(setdist[i])
    '''data output'''
    
    return 0

def binary_heap_building(dataset):
    for i in [len(dataset)-x-1 for x in range(len(dataset))]:
        if(dataset[i][1]<dataset[int(i/2)][1]):
            trans=dataset[i]
            dataset[i]=dataset[int(i/2)]
            dataset[int(i/2)]=trans
    return dataset

def binary_heap_sorting(dataset):
    lenth=len(dataset)
    dataset.insert(0,[-1,-1])
    dataset=binary_heap_building(dataset)
    parameter=0
    ndataset=[[]]

    for i in range(lenth):
        if(parameter!=dataset[1][0]):
            for i in range(dataset[1][0]-parameter):
                ndataset.append([])
            parameter=dataset[1][0]
            ndataset[parameter].append(dataset[1])
        else:
            ndataset[parameter].append(dataset[1])
        dataset=binary_heap_deletion(dataset)
    print(1)
    return ndataset

    
def binary_heap_change(dataset,newdata,position):
    biposition=[a[0] for a in dataset].index(position)
    dataset[biposition][1]=newdata
    for i in range(999999):
        if(newdata<dataset[int(biposition/2)][1]):
            trans=dataset[biposition]
            dataset[biposition]=dataset[int(biposition/2)]
            dataset[int(biposition/2)]=trans
            biposition=int(biposition/2)
            
        elif(biposition*2<len(dataset) and biposition*2+1<len(dataset) and (newdata>dataset[biposition*2][1] or newdata>dataset[biposition*2+1][1])):
            if(dataset[biposition*2][1]>=dataset[biposition*2+1][1]):
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2+1]
                dataset[biposition*2+1]=trans
                biposition=biposition*2+1
            else:
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2]
                dataset[biposition*2]=trans
                biposition=biposition*2
        else:
            break
    return dataset

    
    
def binary_heap_deletion(dataset):
    newdata=dataset[-1][1]
    trans=dataset[1]
    dataset[1]=dataset[-1]
    dataset[-1]=trans
    dataset.pop(-1)
    biposition=1
    for i in range(999999):
        if(biposition*2<len(dataset) and biposition*2+1<len(dataset) and (newdata>dataset[biposition*2][1] or newdata>dataset[biposition*2+1][1])):
            if(dataset[biposition*2][1]>=dataset[biposition*2+1][1]):
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2+1]
                dataset[biposition*2+1]=trans
                biposition=biposition*2+1
            else:
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2]
                dataset[biposition*2]=trans
                biposition=biposition*2
        else:
            break
    return dataset

def binary_heap_add(dataset,newdata,position):
    dataset.append([position,newdata])
    biposition=len(dataset)-1
    for i in range(999999):
        if(newdata<dataset[int(biposition/2)][1]):
            trans=dataset[biposition]
            dataset[biposition]=dataset[int(biposition/2)]
            dataset[int(biposition/2)]=trans
            biposition=int(biposition/2)
        else:
            break
    return dataset

    
    
main()
'''elapsed = (time.clock() - start)
print("Time used:",elapsed)'''

Submission status: Accepted

Solution code:
import time
start=time.clock()
def main():
    [V,E,r]=input().split(" ")
    V=int(V)
    E=int(E)
    r=int(r)
    edgeset=[]
    for i in range(E):
        [s,t,d]=input().split(" ")
        edgeset.append([int(s),int(t),int(d)])
    '''read the edge information and put them to edgeset'''
    
    edgeset.sort()
    edgeset=reform(edgeset)

    setS=[]
    setV=[]
    setdist=[500000*10000+1 for i in range(V)]
    '''generate the sets for optimized vertices, unoptimized vertices, distance respectively'''

    setS.append(r)
    setV.append([r,0])
    setdist[r]=0
    '''initiating data'''

    for i in range(9999999999):
        nowvert=setS[-1]
        for j in range(len(edgeset[nowvert])):
            newdist=edgeset[nowvert][j][2]+setdist[nowvert]
            olddist=setdist[edgeset[nowvert][j][1]]
            '''calculating the new distance including the on process vertices'''
            if(newdist<olddist):
                setdist[edgeset[nowvert][j][1]]=newdist
                setV=binary_heap_add(setV,newdist,edgeset[nowvert][j][1])
            '''making comparision to determin which to stay'''
        if(setV==[[r,0]]):
            break
        setS.append(setV[1][0])
        setV=binary_heap_deletion(setV)
        '''find the next on process vertice'''
                    
    for i in range(V):
        if(setdist[i]==500000*10000+1):
            print('INF')
        else:
            print(setdist[i])
    '''data output'''
    
    return 0

def binary_heap_building(dataset):
    for i in [len(dataset)-x-1 for x in range(len(dataset))]:
        if(dataset[i][1]<dataset[int(i/2)][1]):
            trans=dataset[i]
            dataset[i]=dataset[int(i/2)]
            dataset[int(i/2)]=trans
    return dataset

def reform(dataset):
    lenth=len(dataset)
    parameter=0
    ndataset=[[]]

    for i in range(lenth):
        if(parameter!=dataset[i][0]):
            for j in range(dataset[i][0]-parameter):
                ndataset.append([])
            parameter=dataset[i][0]
            ndataset[parameter].append(dataset[i])
        else:
            ndataset[parameter].append(dataset[i])

    for i in range(lenth-parameter):
        ndataset.append([])
            
    return ndataset

    
def binary_heap_change(dataset,newdata,position):
    biposition=[a[0] for a in dataset].index(position)
    dataset[biposition][1]=newdata
    for i in range(999999):
        if(newdata<dataset[int(biposition/2)][1]):
            trans=dataset[biposition]
            dataset[biposition]=dataset[int(biposition/2)]
            dataset[int(biposition/2)]=trans
            biposition=int(biposition/2)
            
        elif(biposition*2<len(dataset) and biposition*2+1<len(dataset) and (newdata>dataset[biposition*2][1] or newdata>dataset[biposition*2+1][1])):
            if(dataset[biposition*2][1]>=dataset[biposition*2+1][1]):
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2+1]
                dataset[biposition*2+1]=trans
                biposition=biposition*2+1
            else:
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2]
                dataset[biposition*2]=trans
                biposition=biposition*2
        else:
            break
    return dataset

    
    
def binary_heap_deletion(dataset):
    newdata=dataset[-1][1]
    trans=dataset[1]
    dataset[1]=dataset[-1]
    dataset[-1]=trans
    dataset.pop(-1)
    biposition=1
    for i in range(999999):
        if(biposition*2<len(dataset) and biposition*2+1<len(dataset) and (newdata>dataset[biposition*2][1] or newdata>dataset[biposition*2+1][1])):
            if(dataset[biposition*2][1]>=dataset[biposition*2+1][1]):
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2+1]
                dataset[biposition*2+1]=trans
                biposition=biposition*2+1
            else:
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2]
                dataset[biposition*2]=trans
                biposition=biposition*2
        else:
            break
    return dataset

def binary_heap_add(dataset,newdata,position):
    dataset.append([position,newdata])
    biposition=len(dataset)-1
    for i in range(999999):
        if(newdata<dataset[int(biposition/2)][1]):
            trans=dataset[biposition]
            dataset[biposition]=dataset[int(biposition/2)]
            dataset[int(biposition/2)]=trans
            biposition=int(biposition/2)
        else:
            break
    return dataset

    
    
main()
'''elapsed = (time.clock() - start)
print("Time used:",elapsed)'''

Submission status: Accepted

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

import sys
from collections import deque
import heapq
from collections import Counter
import math

# ------------------------------------------------------
class IN:
    @staticmethod
    def singleInt():
        return int(input())

    @staticmethod
    def singleStr():
        return input()

    @staticmethod
    def listInt():
        return list(map(int, input().split()))

    @staticmethod
    def listStr():
        return input().split()
# ------------------------------------------------------

print = lambda s: sys.stdout.write(str(s) + "\r\n")

def contain(c, x):
    return (x in c)

def str_reverse(s):
    return s[::-1]

def ctoi(c):
    return int.from_bytes(c.encode(), byteorder='big')
def itoc(x):
    return x.to_bytes((x.bit_length() + 7) // 8, byteorder='big').decode()

INF = 1001001001001001001
MOD = 1000000007
# ------------------------------------------------------

if __name__ == '__main__':
    N, M, S = IN.listInt()
    g = [[] for i in range(N)]
    for i in range(M):
        a, b, c = IN.listInt()
        g[a].append((b, c))
    
    hp = []
    dist = [INF for i in range(N)]
    heapq.heappush(hp, (0, S))
    dist[S] = 0
    while len(hp) > 0:
        _, v = heapq.heappop(hp)
        for (w, c) in g[v]:
            if dist[w] > dist[v] + c:
                dist[w] = dist[v] + c
                heapq.heappush(hp, (dist[w], w))

    for i in range(N):
        if dist[i] == INF:
            print("INF")
        else:
            print(dist[i])

Submission status: Accepted

Solution code:
import queue

def Dijkstra(vertex,edges,start):
	weight = [0 if i==start else float("inf") for i in range(vertex)]
	Q = queue.PriorityQueue()
	Q.put((weight[start],start))

	while(not Q.empty()):
		cur = Q.get()
		if weight[cur[1]] < cur[0]:
			continue
		for j in range(len(edges[cur[1]])):
			if weight[edges[cur[1]][j][1]] > weight[cur[1]] + edges[cur[1]][j][2]:
				weight[edges[cur[1]][j][1]] = weight[cur[1]] + edges[cur[1]][j][2]
				Q.put((weight[edges[cur[1]][j][1]],edges[cur[1]][j][1]))
	return weight

V,E,r = map(int,input().split())
edges = [[] for i in range(V)]
for i in range(E):
	data = list(map(int,input().split()))
	edges[data[0]].append(data)
for j in range(V):
	edges[j].sort()
w = Dijkstra(V,edges,r)
for i in range(len(w)):
	if w[i]==float("inf"):
		print('INF')
	else:
		print(w[i])

Submission status: Accepted

Solution code:
import sys
from heapq import heappush
from heapq import heappop


# 入力
n_V, n_E, r = map(int, input().split())

E = [[] for _ in range(n_V)]
for i in range(n_E):
    v, e, c = map(int, input().split())
    E[v].append((e, c))


# 初期化
D = [sys.maxsize for _ in range(n_V)]
D[r] = 0

h = []
heappush(h, (D[r], r))


#　各頂点への最短距離を求める処理
while len(h) != 0:
    _, index = heappop(h)

    for e, c in E[index]:
        d = D[index] + c
        if D[e] > d:
            D[e] = d
            heappush(h, (d, e))


# 出力
for d in D:
    if d == sys.maxsize:
        print('INF')
    else:
        print(d)

Submission status: Accepted

Solution code:

v, e, r = map(int, input().split()) # 頂点数v,辺数e,始点rを入力

g = [[] for i in range(v)] # グラフ

for i in range(e):
 s, t, d = map(int, input().split())
 g[s].append([t,d]) # sからtへの辺とその重みd


cost = ['INF' for i in range(v)] # 出力結果を初期化
cost[r] = 0
finish = [] # 最低コストが確定した頂点
finish.append(r)

import heapq
h = []

u = r # 新しく確定した頂点

for count in range(v-1):

 for adj in g[u]:
  if cost[ adj[0] ] != 'INF':
   continue

  new_cost = cost[u] + adj[1]
  heapq.heappush(h, (new_cost, adj[0]))
  

 while 1:
  if len(h) == 0:
   break

  minc = heapq.heappop(h)
  if cost[ minc[1] ] == 'INF':
   cost[ minc[1] ] = minc[0]
   u = minc[1]
   break

for i in range(v):
 print(cost[i])

Submission status: Accepted

Solution code:

v, e, r = map(int, input().split()) # 頂点数v,辺数e,始点rを入力

g = [[] for i in range(v)] # グラフ

for i in range(e):
 s, t, d = map(int, input().split())
 g[s].append([t,d]) # sからtへの辺とその重みd


cost = ['INF' for i in range(v)] # 出力結果を初期化
cost[r] = 0

import heapq
h = []

u = r # 新しく確定した頂点

for count in range(v-1):

 for adj in g[u]:
  if cost[ adj[0] ] != 'INF':
   continue

  new_cost = cost[u] + adj[1]
  heapq.heappush(h, (new_cost, adj[0]))
  
  
 while 1:
  if len(h) == 0:
   break

  minc = heapq.heappop(h)
  if cost[ minc[1] ] == 'INF':
   cost[ minc[1] ] = minc[0]
   u = minc[1]
   break


for i in range(v):
 print(cost[i])

Submission status: Accepted

Solution code:
# Single Source Shortest Path
import heapq

[vertex, edge, r] = list(map(int, input("").split()))
infty = 999999999
final_c = [infty for i in range(vertex)]
dict_c = [[] for i in range(vertex)]

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    dict_c[e1].append((e2, c))

final_c[r] = 0
root_c = [(final_c[r], r)]

def Dijkstra(root, n):
    global infty, root_c, final_c, dict_c, root_c
    while(root_c):
        (cost, v) = heapq.heappop(root_c)
        if cost > final_c[v]:
            continue
        for i in range(len(dict_c[v])):
            (e2, c) = dict_c[v][i]
            if final_c[e2] > final_c[v] + c:
                final_c[e2] = final_c[v] + c
                heapq.heappush(root_c, (final_c[e2], e2))

Dijkstra(r, vertex)
for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print(final_c[i])

Submission status: Accepted

Solution code:
import heapq

nv,ne,r = map(int, input().split())

nodes = [[] for _ in range(nv)]

for _ in range(ne):
    s,t,d = map(int, input().split())
    nodes[s].append((d, t))


costs = [-1] * nv
costs[r] = 0
hq = nodes[r]

while hq:
    cost, index = heapq.heappop(hq)
    if costs[index] > -1:
        continue
    costs[index] = cost
    for weight, next_index in nodes[index]:
        if costs[next_index] == -1:
            heapq.heappush(hq, (cost + weight, next_index))

for cost in costs:
    if cost == -1:
        print('INF')
        continue
    print(cost)

Submission status: Accepted

Solution code:
import queue


def dijkstra(n, graph, start):
    dist = [0 if i == start else float('inf') for i in range(n)]
    que = queue.PriorityQueue()
    que.put((0, start))

    while not que.empty():
        p = que.get()
        d, now = p[0], p[1]

        if dist[now] < d:
            continue

        for e in graph[now]:
            if dist[e[0]] <= d + e[1]:
                continue

            dist[e[0]] = dist[now] + e[1]
            que.put((dist[e[0]], e[0]))

    return dist


def main():
    n, m, s = map(int, input().split())
    graph = [[] for _ in range(n)]

    for _ in range(m):
        data = list(map(int, input().split()))

        graph[data[0]].append([data[1], data[2]])

    dist = dijkstra(n, graph, s)

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def bellmanford(G,s):
    n = len(G)
    dist = [float("inf") for i in range(n)]
    dist[s]=0
    for k in range(n):
        flag = False
        for u in range(n):
            for v in range(len(G[u])):
                if dist[G[u][v][0]]>dist[u]+G[u][v][1]:
                    dist[G[u][v][0]]=dist[u]+G[u][v][1]
                    flag = True
        if(not flag):break
    for k in dist:
        if(k==float("inf")):print("INF")
        else:print(k)
                    
                        
def main():
    T =[int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    s = T[2]
    G = [[] for i in range(V)]
    
    for i in range(E):
        line = [int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append((line[1],line[2]))
    bellmanford(G,s)
main()

Submission status: Accepted

Solution code:
from heapq import heappop as pop
from heapq import heappush as push

INF = 10 ** 18

class edge:
  def __init__(self, to, cost):
    self.to = to
    self.cost = cost

V, E, r = map(int,input().split())

G = [[] for i in range(V)]
#G[i]...頂点iからの辺、(行き先、コスト)
d = [0 for i in range(V)]
#d[i]...スタートからみた頂点iまでの最短距離

def dijkstra(s, V):
  que = []
  global d
  global G
  d = [INF for i in range(V)]
  d[s] = 0
  push(que, (0,s))

  while len(que):
    p = pop(que)
    v = p[1]
    if (d[v] < p[0]):
      continue
#    print(p)
    for i in range(len(G[v])):
      e = G[v][i]
      if d[e.to] > d[v] + e.cost:
        d[e.to] = d[v] + e.cost
        push(que, (d[e.to], e.to))

for i in range(E):
  s, t, c = map(int,input().split())
  G[s].append(edge(t,c))
dijkstra(r, V)

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

Submission status: Accepted

Solution code:
import sys
import heapq
def Dj(G,s):
    n = len(G)
    dist = [float("inf") for i in range(n)]
    vis = [-1 for i in range(n)]
    li = [(0,s)]
    dist[s]=0
    heapq.heapify(li)
    while len(li):
        d,u = heapq.heappop(li)
        if vis[u]==1:
            continue
        vis[u]=1
        for v in G[u]:
            if dist[v[1]]>dist[u] + v[0]:
                dist[v[1]] = dist[u] + v[0]
                heapq.heappush(li,(dist[u] + v[0],v[1]))
    return dist
                
    
    

def main():
    T = [int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    S = T[2]
    G = [[] for i in range(V)]
    for i in range(E):
        line = [int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append((line[2],line[1]))
    for k in Dj(G,S):
        if k ==float("inf"):print("INF")
        else:print(k)
main()

Submission status: Accepted

Solution code:
import heapq
from typing import List, TypeVar, Generic
T = TypeVar('T', int, float)


class Edge(Generic[T]):
    def __init__(self, dst: int, weight: T) -> None:
        self.dst: int = dst
        self.weight: T = weight

    def __lt__(self, e: 'Edge') -> bool:
        return self.weight > e.weight


class Graph(Generic[T]):
    def __init__(self, V: int) -> None:
        self.V: int = V
        self.E: List[List[Edge[T]]] = [[] for _ in range(V)]

    def add_edge(self, src: int, dst: int, weight: T) -> None:
        self.E[src].append(Edge(dst, weight))


class Node(Generic[T]):
    def __init__(self, v: int, cost: T) -> None:
        self.v: int = v
        self.cost: T = cost

    def __lt__(self, n: 'Node') -> bool:
        return self.cost < n.cost


class ShortestPath(Generic[T]):
    def __init__(self, G: Graph[T], inf: T = 10**9) -> None:
        self.G: Graph[T] = G
        self.inf: T = inf
        self.dist: List[T] = [self.inf] * self.G.V  # distance from start
        self.prev: List[int] = [-1] * self.G.V  # prev vertex of shortest path

    def run(self, start: int, goal: int = -1) -> None:
        que: List[Node] = list()
        self.dist[start] = 0
        heapq.heappush(que, Node[T](start, 0))

        while que:
            node: Node[T] = heapq.heappop(que)
            if self.dist[node.v] < node.cost:
                continue
            if goal != -1 and node.v == goal:
                return
            for edge in self.G.E[node.v]:
                if self.dist[node.v] + edge.weight < self.dist[edge.dst]:
                    self.dist[edge.dst] = self.dist[node.v] + edge.weight
                    heapq.heappush(que, Node(edge.dst, self.dist[edge.dst]))
                    self.prev[edge.dst] = node.v

    def getPath(self, end: int) -> List[int]:
        path: List[int] = [end]
        while self.prev[end] != -1:
            end = self.prev[end]
        return path[::-1]

def main() -> None:
    V, E, start = map(int, input().split())
    graph = Graph[int](V)
    for _ in range(E):
        s, t, d = map(int, input().split())
        graph.add_edge(s, t, d)
    inf = int(1e10)
    sp = ShortestPath[int](graph, inf)
    sp.run(start)
    for i in range(V):
        print(sp.dist[i] if sp.dist[i] != inf else "INF")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10 ** 20

v_num, e_num, r = map(int, input().split())
edges_lst = [[] for _ in range(v_num)]
dist_lst = [INF for _ in range(v_num)]

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

que = []
heappush(que, (0, r))
dist_lst[r] = 0

while que:
  dist, node = heappop(que)
  for to, cost in edges_lst[node]:
    if dist_lst[to] > cost + dist:
      dist_lst[to] = cost + dist
      heappush(que, (cost + dist, to))

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

v,e,r=map(int, input().split());

edge_info=[0]*v;
for i in range(v):
    edge_info[i] = []

for i in range(e):
    e1, e2, w = map(int, input().split());
    edge_info[e1].append((e2,w))

v_q=deque();

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
v_q.append((0,r))
while(len(v_q) != 0):
    cost,u = v_q.popleft()
    if(cost > d[u]):
        continue
    for j in range(len(edge_info[u])):
        e2,w = edge_info[u][j]
        alt = cost+w
        if(d[e2] > alt):
            d[e2] = alt
            v_q.append((alt,e2))

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

v,e,r=map(int, input().split());

edge_info=[0]*v;
for i in range(v):
    edge_info[i] = []

for i in range(e):
    e1, e2, w = map(int, input().split());
    edge_info[e1].append((e2,w))

v_q=deque();

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
v_q.append((0,r))
while(len(v_q) != 0):
    cost,u = v_q.popleft()
    if(cost > d[u]):
        continue
    for j in range(len(edge_info[u])):
        e2,w = edge_info[u][j]
        alt = cost+w
        if(d[e2] > alt):
            d[e2] = alt
            v_q.append((alt,e2))

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

Submission status: Accepted

Solution code:
import heapq
from enum import Enum, auto

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

class Node:
    def __init__(self, n, w):
        self.n = n
        self.w = w

    def __lt__(self, node):
        return self.w < node.w

color = []      # 探索状態
d = []          # コスト

# input
V, E, r = list(map(int, input().split(' ')))
adj_list = [[] for i in range(V)]
for i in range(E):
    s, t, d = list(map(int, input().split(' ')))
    adj_list[s].append([t, d])

def dijkstra(s):
    global d, color
    color = [Color.WHITE for i in range(V)]
    d = [float('inf') for i in range(V)]
    d[s] = 0

    pqueue = [Node(s, 0)]
    while len(pqueue) >= 1:
        u = heapq.heappop(pqueue).n
        color[u] = Color.BLACK

        for v, w in adj_list[u]:
            if color[v] != Color.BLACK:
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    color[v] = Color.GRAY
                    heapq.heappush(pqueue, Node(v, d[v]))

dijkstra(r)
for w in d:
    if w == float('inf'):
        print('INF')
    else:
        print(w)

Submission status: Accepted

Solution code:

#Bellman-FordだとTLEになる(はず)
V,E,r = map(int, input().split())
edges = []
for _ in range(E):
    tmp = [int(x) for x in input().split()]
    edges.append(tmp)

d = [float('inf') for _ in range(V)]
d[r] = 0

for _ in range(V-1):
    count = 0
    for x in edges:
        s,t,w = x
        if d[t] > d[s] + w:
            count += 1
            d[t] = d[s] + w
    if count == 0:
        break

for x in d:
    if x == float('inf'):
        print('INF')
    else:
        print(x)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import math

if __name__ == '__main__':
    V, E, r = map(int, input().split())
    edge = [[] for _ in range(V)]
    d = [math.inf] * V
    que = []
    for _ in range(E):
        s, t, c = map(int, input().split())
        edge[s].append([t, c])

    d[r] = 0
    heap = [(d[r], r)]
    while heap:
        du, u = heappop(heap)
        for t, c in edge[u]:
            if d[t] > du + c:
                d[t] = du + c
                heappush(heap, (d[t], t))

    for di in d:
        print('INF' if math.isinf(di) else di)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = float('inf')
def dijkstra(s, n, adj):
    dist = [INF] * n
    hq = [(0, s)]
    dist[s] = 0
    seen = [False] * n
    while hq:
        v = heappop(hq)[1]
        seen[v] = True
        for to, cost in adj[v]:
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

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

ans = dijkstra(r, v, adj)
for i in ans:
    if i == float('inf'):
        print('INF')
    else:
        print(i)

Submission status: Accepted

Solution code:
import sys
import heapq

V, E, r = map(int, sys.stdin.readline().strip().split())

G = [[] for _ in range(V)]
for e in range(E):
    s, t, d = map(int, sys.stdin.readline().strip().split())

    G[s].append((t, d))
    # G[t].append((s, d))


distance = ['INF'] * V  # 何らかの数値: 探索済み  INF: 未探索
distance[r] = 0
que = []

for u, d_u in G[r]:
    heapq.heappush(que, (d_u, u))

while que:
    d_tot, u = heapq.heappop(que)
    if distance[u] is not 'INF':
        continue

    distance[u] = d_tot
    for v, d_v in G[u]:
        if distance[v] is not 'INF':  # v にすでに訪問済みであった場合
            continue
        heapq.heappush(que, (d_tot + d_v, v))

for i in distance:
    print(i)

Submission status: Accepted

Solution code:
def dijkstra(vertex_num, edge_list, start):
    import heapq
    # cost to each vertex
    d = [float("inf")] * vertex_num
    # start cost is zero
    d[start] = 0
    hq = []
    heapq.heappush(hq, [0, start])
    while len(hq) > 0:
        cost, frm = heapq.heappop(hq)
        for cost, to in edge_list[frm]:
            if d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                heapq.heappush(hq, [d[to], to])
    return d

n, m, s = map(int, input().split())

adj_list = [[] for _ in range(n)]

for i in range(m):
    frm, to, cost = map(int, input().split())
    adj_list[frm].append([cost, to])

d = dijkstra(n, adj_list, s)

for i in range(len(d)):
    print(d[i]) if d[i] != float("inf") else print("INF")

Submission status: Accepted

Solution code:
# 56

# from collections import deque
import heapq

v, e, r = map(int, input().split())

# g_m = [[float("INF")] * v for _ in range(v)]
g_l = [[] for _ in range(v)]

for i in range(e):
    _s, _t, _d = map(int, input().split())
#     g_m[_s][_t] = _d
    g_l[_s].append([_t,_d])

def djkstra(s):
    ans_l = [float("INF")] * v
    _l = [[0,s]]
    heapq.heapify(_l)
    while len(_l) > 0:
        _c, _v = heapq.heappop(_l)
        if ans_l[_v] < _c:
            continue
        ans_l[_v] = _c
        for _t, _d in g_l[_v]:
            if ans_l[_t] > _c + _d:
                heapq.heappush(_l,[_c + _d, _t])
    return ans_l

ans_l = djkstra(r)
for i in range(v):
    print(str(ans_l[i]).upper())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from pprint import pprint
import heapq
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


N, M, source = map(int, input().split())
adj_list = [[] for v in range(N)]
for _ in range(M):
    u, v, w = map(int, input().split())
    adj_list[u].append([v, w])
# pprint(adj_list)


def dijkstra(n_nodes, adj_list, source):
    dist = [0 if v == source else INF for v in range(n_nodes)]
    priority_queue = [[dist[source], source]]

    while priority_queue:
        current_distance, current = heapq.heappop(priority_queue)
        if current_distance > dist[current]:
            continue
        for neighbor, distance in adj_list[current]:
            if current_distance + distance < dist[neighbor]:
                dist[neighbor] = current_distance + distance
                heapq.heappush(priority_queue, [dist[neighbor], neighbor])

    return dist


dist = dijkstra(N, adj_list, source)

for v in range(N):
    if dist[v] == INF:
        print('INF')
    else:
        print(dist[v])