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 heapq

v, e, r = map(int, input().split()) #頂点の数、辺の数、始点
edges = [[] for _ in range(v)] #始点別、終点、コスト
for i in range(e):
    s, t, d = map(int, input().split())
    edges[s].append([t,d])

def dijkstra(edges, start, num_v):
    dist = [float('INF')]*num_v #各点までの最短距離リスト、初期値無限大
    dist[start] = 0 #始点までの距離 = 0
    q = []
    heapq.heappush(q, [0,start])
    
    while q:
        _, u = heapq.heappop(q)
        for i in edges[u]:
            if dist[i[0]] > dist[u] + i[1]:
                dist[i[0]] = dist[u] + i[1]
                heapq.heappush(q, [dist[u] + i[1], i[0]])
    return dist

res = dijkstra(edges, r, v)
for i in range(v):
    if res[i] == float('inf'):
        print('INF')
    else:
        print(res[i])

Submission status: Accepted

Solution code:
import heapq

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

    def __str__(self):
        return "id: {}\t weight:{}".format(self.id, self.weight)

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

class WeightDirectedGraph():    
    def __init__(self, V):
        self.G = {i: [] for i in range(V)}
        self.V = V
        self.INF = 10**10

    def append(self, a, b, w):
        self.G[a].append(Node(b, w))

    def dijkstra(self, s):
        # distance from s
        D = [self.INF] * self.V
        D[s] = 0

        # node with minimum distance
        H = []
        heapq.heappush(H, Node(s, D[s]))

        while len(H) > 0:
            u = heapq.heappop(H)
            if D[u.id] >= u.weight:
                # update distance
                for v in self.G[u.id]:
                    w = u.weight + v.weight
                    if D[v.id] > w:
                        D[v.id] = w
                        heapq.heappush(H, Node(v.id, D[v.id]))
        return D


V,E,r = map(int, raw_input().split())
G = WeightDirectedGraph(V)
for i in range(E):
    s,t,d = map(int, raw_input().split())
    G.append(s,t,d)

for d in G.dijkstra(r):
    if d == G.INF:
        print "INF"
    else:
        print d

Submission status: Accepted

Solution code:
import heapq
def solve(V,E,r,adjlist):
    cost=[float('inf')]*V
    used=[False]*V
    cost[r]=0
    used[r]=True
    h=[]
    for v in adjlist[r]:
        heapq.heappush(h,v)
    while(len(h)>0):
        u=heapq.heappop(h)
        if used[u[1]]:
            continue
        used[u[1]]=True
        cost[u[1]]=u[0]
        for d,t in adjlist[u[1]]:
            if cost[t]>u[0]+d:
                cost[t]=u[0]+d
                heapq.heappush(h,tuple((cost[t],t)))
    return cost





V,E,r=map(int,input().split())
adjlist=[[] for _ in range(V)]
for _ in range(E):
    s,t,d=map(int,input().split())
    adjlist[s].append(tuple((d,t)))
ans=solve(V,E,r,adjlist)
for i in range(V):
    if ans[i]==float('inf'):
        print("INF")
    else:
        print(ans[i])

Submission status: Accepted

Solution code:
import heapq

N, M, r = map(int, input().split())
inf = 10 ** 18

def dijkstra(start):
    q = [(0, start)]
    heapq.heapify(q)
    cost = [inf] * N
    cost[start] = 0
    while q:
        c, v = heapq.heappop(q)
        if c > cost[v]:
            continue
        for d, u in G[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(q, (tmp, u))
    return cost

# G = [(cost, edge), ...]
G = [[] for _ in range(N)]
for _ in range(M):
    a, b, t = map(int, input().split())
    # a, b = a - 1, b - 1
    G[a].append((t, b))
    # G[b].append((t, a))

res = dijkstra(r)
for i in res:
    if i == inf:
        print("INF")
        continue
    print(i)

Submission status: Accepted

Solution code:
from heapq import  heappop, heappush
def dijkstra(edges,start,first_index=0):
    d=[-1]*(len(edges)+first_index)
    hq=[(0,start)]
    while hq:
        c,v=heappop(hq)
        if d[v]!=-1:continue
        d[v]=c
        for to,cos in edges[v]:
            if d[to]==-1:heappush(hq,(c+cos,to))
    return d
v,e,st,*l=map(int,open(0).read().split())
ed=[[] for i in range(v)]
for a,s,d in zip(*[iter(l)]*3):
    ed[a].append((s,d))

for i in dijkstra(ed,st):
    print("INF"if -1==i else i )

Submission status: Accepted

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

edge=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  edge[a].append((b,c))
#print(edge)

from heapq import heappop,heappush
ans=[10 ** 20] * n
ans[s]=0
h=[[0,s]]
while h:
  c, v = heappop(h)
  if ans[v] < c:
    continue
  for u,t in edge[v]:
    if c + t < ans[u]:
      ans[u] = c + t
      heappush(h,[c + t,u])
#出力
for i in ans:
  if i == 10 ** 20:
    print("INF")
  else:print(i)

Submission status: Accepted

Solution code:
import heapq

if __name__ == "__main__":
    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))
    
    d = [float('inf')] * v
    d[r] = 0

    hq = [(0, r)]
    heapq.heapify(hq)

    while hq:
        cost, now = heapq.heappop(hq)
        if d[now] < cost:
            continue

        for nei in graph[now]:
            to = nei[0]
            c = nei[1]
            if d[to] > d[now] + c:
                d[to] = d[now] + c
                heapq.heappush(hq, (d[to], to))
    for i in range(v):
        if d[i] == float('inf'):
            print("INF")
        else:
            print(d[i])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

edges = defaultdict(set)

for _ in range(E):
    s, t, d = map(int, input().split(' '))
    edges[s].add((t, d))

costs = [-1] * V
costs[r] = 0

queue = deque()
queue.append(r)

while len(queue) > 0:
    s = queue.popleft()
    for t, d in edges[s]:
        if costs[t] < 0 or costs[s] + d < costs[t]:
            costs[t] = costs[s] + d
            queue.append(t)

for i in range(V):
    if costs[i] < 0:
        print('INF')
    else:
        print(costs[i])

Submission status: Accepted

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
from queue import PriorityQueue
import itertools
from copy import deepcopy
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
class Edge():
    def __init__(self,x,y,cost=1):
        self.x=x
        self.y=y
        self.cost=cost
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def ispow(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def lcm(a,b):
    return a*b//math.gcd(a,b)
    G=[[] for a in range(n)]
    for edge in edges:
        x=edge[0]
        y=edge[1]
        G[x].append(y)
        if mukou:G[y].append(x)
    return G
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.cost))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.cost,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
######################################################################################################
V,E,start=inputintlist()
edges=[]
for a in range(E):
    e=Edge(*inputintlist())
    edges.append(e)

mincost=dijkstra(edges,V,start)
for a in range(len(mincost)):
    print(ifelse(mincost[a]==inf,"INF",mincost[a]))

Submission status: Accepted

Solution code:
# ダイクストラ法の練習に．
from heapq import heapify, heappop, heappush


def main():
    vertex, edge, root = map(int, input().split())
    max_val = 10 ** 10
    graph = [[] for _ in range(vertex)]
    for _ in range(edge):
        s, t, d = map(int, input().split())
        graph[s].append((t, d))
    dist = [max_val for _ in range(vertex)]
    dist[root] = 0
    q = []
    heapify(q)
    heappush(q, (0, root))
    while q:
        now_d, now_v = heappop(q)
        for next_v, length in graph[now_v]:
            now_dist = dist[now_v] + length
            if dist[next_v] > now_dist:
                dist[next_v] = now_dist
                heappush(q, (dist[next_v], next_v))

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

v, e, r = map(int, input().split())
g = [[] for _ in range(v)]
for i in range(e):
    s, t, d = map(int, input().split())
    g[s].append((d, t))#(重み, 次の頂点)

dist = [float("inf")] * v
visited = [False] * v
dist[r] = 0
visited[r] = True
candidate = []
for i in g[r]:
    heapq.heappush(candidate, i)
while len(candidate):
    #まだ使われていない頂点から最小のものを探す
    minedge = heapq.heappop(candidate)#(重み, 頂点)
    if visited[minedge[1]]:
        continue
    c = minedge[1]
    dist[c] = minedge[0]
    visited[c] = True
    for i in g[c]:
        if not visited[i[1]]:
            heapq.heappush(candidate, (dist[c] + i[0], i[1]))

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m,r = map(int,readline().split())
g = [[] for i in range(n)]
for i in range(m):
    x,y,w = map(int,readline().split())
    g[x].append((w,y))
    #g[y].append((w,x))

#新ダイクストラ
INF = 10**18
import heapq
push = heapq.heappush
pop = heapq.heappop
def dijkstra(s,g): #g:(weight,go)の順の隣接リスト※タプルで有ることに注意
    n = len(g)
    dist = [INF]*n
    dist[s] = 0
    used = [0]*n
    used[s] = 1
    hp = []
    for go in g[s]:
        push(hp,go)
    while hp:
        w,fr = pop(hp)

        if not used[fr]:
            dist[fr] = w
            used[fr] = 1
            for w,go in g[fr]:
                if not used[go]:
                    push(hp,(w+dist[fr],go))
    
    return dist

for i in dijkstra(r,g):
    print(i if i < INF else "INF")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from  heapq import heappush, heappop
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def main():
  V, E, r = LI()
  INF = 10**12

  if V == 1:
    print(0)
    exit()

  # 隣接リスト
  adj = [[] for _ in range(V)]

  for i in range(E):
    s, t, d = LI()
    adj[s].append((t,d))

  # 初期状態
  q = [(0,r)]
  C = [INF] * V# 始点から各頂点までのコスト
  C[r] = 0

  # 本処理
  while len(q) > 0:
    # 未訪問かつ一番コストが小さいものをuとする
    cost, u = heappop(q)
  
    for v,d in adj[u]:
      tmp = C[u] + d
      if tmp < C[v]:
        C[v] = tmp
        heappush(q, (C[v], v))

  for c in C:
    if c == INF:
      print('INF')
    else:
      print(c)
    
#Solve
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=ja

# ダイクストラ
from heapq import heappush, heappop


class PriorityQueue:
    def __init__(self):
        self._queue = []

    def push(self, value):
        heappush(self._queue, value)

    def pop(self):
        return heappop(self._queue)

    @property
    def empty(self):
        return not self._queue

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

    def __contains__(self, item):
        return item in self._queue


V, E, R = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    f, t, d = map(int, input().split())
    edge[f].append((d, t))

queue = PriorityQueue()
queue.push((0, R))
visited = [float('inf')] * V
visited[R] = 0

while True:
    d, v = queue.pop()
    dist = visited[v]
    for e in edge[v]:
        if (e[0] + dist) < visited[e[1]]:
            visited[e[1]] = e[0] + dist
            queue.push((e[0] + dist, e[1]))

    if queue.empty:
        break
        
for i in visited:
    if i == float('inf'):
        print('INF')
    else:
        print(i)

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

inf = float("inf")
def dijkstra(graph, start):  # graphは隣接リスト(繋がっている先, コスト)
    vsize = len(graph)
    dist = [inf] * vsize
    seen = [False] * vsize
    pq = []
    heapify(pq)

    dist[start] = 0
    heappush(pq, (0, start))  # heapではtuple[0]で比較されるのでこの順番で追加する
    while pq:
        cost, u = heappop(pq)
        seen[u] = True
        if dist[u] < cost:
            continue
        for v, w in graph[u]:
            temp_cost = dist[u] + w
            if not seen[v] and temp_cost < dist[v]:
                dist[v] = temp_cost
                heappush(pq, (dist[v], v))
    return dist
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))
for min_cost in dijkstra(graph, r):
    print(min_cost if min_cost != inf else "INF")

Submission status: Accepted

Solution code:
import heapq

INF = 10 ** 9

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


# 終点を渡す
def dijkstra(x):
    d = [INF] * x # dist
    d[r] = 0 # r = 0
    hq = [(0, r)] # (dist, v)

    while hq:
        c, v = heapq.heappop(hq) # pop

        if d[v] < c: # seen の役割
            continue

        for t, cost in adjw[v]: # 隣接しているノードについて
            if d[v] + cost < d[t]:
                d[t] = d[v] + cost
                heapq.heappush(hq, (d[t], t))
    
    return d

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

Submission status: Accepted

Solution code:
import heapq

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

g = [[] for _ in range(V)]
for i in range(E):
    s, t, d = map(int, input().split())
    g[s].append((t, d))

dis = [float("inf") for _ in range(V)]
dis[r] = 0

pq = [(0, r)]
while pq:
    d, node = heapq.heappop(pq)
    if d > dis[node]: continue

    for nxt, cost in g[node]:
        if d + cost < dis[nxt]:
            dis[nxt] = d + cost
            heapq.heappush(pq, (dis[nxt], nxt))

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

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


################################
n,w,r = map(int,input().split()) #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())
    edge[x].append([z,y])
    #edge[y].append([z,x]) 
D=dijkstra_heap(r,edge)


for index in range(n):
    if D[index]==10**20:
        D[index]='INF'
    print(D[index])

Submission status: Accepted

Solution code:
import heapq
def dijkstra(s):
    # 始点sから各頂点への最短距離
    d = [float('inf')]*n
    d[s] = 0
    # 各頂点が訪問済みかどうか
    used = [False]*n
    used[s] = True
    # 仮の距離を記録するヒープ
    que = []
    for e in g[s]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in g[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d

##############################
n, w, r = [int(x) for x in input().split()] # n:頂点数 w:辺の数
g = [[] for _ in range(n)]
# g[i]:iから出る辺の[コスト,行先]
for _ in range(w):
    x, y, z = [int(x) for x in input().split()]
    g[x].append([z, y])
    # g[y].append([z, x])
for i in dijkstra(r):
    if i == float("inf"):
        print("INF")
    else:
        print(i)

Submission status: Accepted

Solution code:

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

INF = 10 ** 15

# ダイクストラのアルゴリズムは
# 再帰
def dijkstra(edges, s):
    d = [INF for x in range(V)]
    d[s] = 0
    que = []
    heapq.heappush(que, (0,s))
    while len(que) > 0:
        u_d,u = heapq.heappop(que)
        if d[u] < u_d:
            continue
        for  v_d,v in edges[u]:
            if d[v] > d[u] + v_d:
                d[v] = d[u] + v_d
                heapq.heappush(que,(d[v],v))
    return d

#cost = [[float("inf") for i in range(V)] for i in range(V)] 
cost = [[] for i in range(V)]
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(E):
    x,y,z = map(int,input().split())
    cost[x].append((z, y))
    #cost[y][x] = z
d = dijkstra(cost, r)
for c in d:
    if c == INF:
        print("INF")
    else:
        print(c)

Submission status: Accepted

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

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

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

def resolve():
    V, E, r = LI()
    std = [LI() for _ in range(E)]

    edge = [[] for _ in range(V)]
    for i in std:
        edge[i[0]].append((i[1], i[2]))

    d = dijkstra(edge, r)

    for i in d:
        if i<INF:
            print(i)
        else:
            print('INF')

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n,m,s=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  edge[a].append((b,c))
from heapq import heappop,heappush
ans=[10**20]*n
ans[s]=0
h=[[0,s]]
while h:
  c,v=heappop(h)
  if ans[v]<c:continue
  for u,t in edge[v]:
    if c+t<ans[u]:
      ans[u]=c+t
      heappush(h,[c+t,u])
for i in ans:
  if i==10**20:print("INF")
  else:print(i)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A
import heapq

N, M, r = list(map(int, input().split()))

D = {}
for i in range(N):
    D[i] = []

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

A = []
heapq.heappush(A, (0, r))

INF = float('inf')
results = [INF for _ in range(N)]
results[r] = 0

while A:
    cost, a = heapq.heappop(A)
    for t, d in D[a]:
        next_cost = cost + d
        if next_cost < results[t]:
            results[t] = next_cost
            heapq.heappush(A, (next_cost, t))

for result in results:
    if result == INF:
        print('INF')
    else:
        print(result)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
INF=10**30

def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        for c,v in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[v],v))
    return dist

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

Submission status: Accepted

Solution code:
from collections import deque

V,E,r = map(int,input().split())
dlis = [[] for _ in range(V)]
mind = [10**10]*V

for _ in range(E):
  std = list(map(int,input().split()))
  dlis[std[0]].append([std[1],std[2]])
  
q = deque()
q.append([r,0])

while len(q) > 0:
  v = q.popleft()
  a = v[0]
  b = v[1]
  if mind[a] <= b:
    continue
  mind[a] = b
  for el in dlis[a]:
    aa = el[0]
    bb = b + el[1]
    if mind[aa] > bb:
      q.append([aa,bb])
    
for i in range(V):
  if mind[i] == 10**10:
    print("INF")
  else:
    print(mind[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(sys.stdin.readline() for _ in range(n)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections
N,E,r = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
sdd = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) # multi line with multi param
#G = [[src1 dist1 d1][src1 dist1 d1]...]# vect source1 -> distance1 distances
G = [[] for i in range(N)]
for src,dist,d in sdd:
  G[src].append((dist,d))
#print(sdd,r,G)
INF = float("inf")
ALL = set(range(N))
mst = set()
#distances = [INF]*N # 蟋狗せr縺九ｉ縺ｮ霍晞屬
distances = collections.defaultdict(lambda:INF)
distances[r] = 0

import heapq

dv = []
def add(u):
  mst.add(u)
  if len(mst) == N: return
  for v,w in G[u]:
    if not v in mst and w + distances[u] < distances[v]: # u繧堤ｵ檎罰縺励◆譁ｹ縺悟ｮ峨＞
      distances[v] = distances[u]+w
      heapq.heappush(dv, (distances[v],v))
  #print(distances)
  #print(u,distances,dv)
  if not dv:
    return None
  d,v = heapq.heappop(dv)
  while dv and v in mst:
    d,v = heapq.heappop(dv)
  if v in mst:
    return None
  return v

n = add(r)
while n != None:
  n = add(n)
  #print("n:",n)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq as hq
INF = 10**10
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((d,t))
    #e[t].append((d,s))
D = [INF] * V
B = [False] * V
h = []
hq.heappush(h, (0, r))
cnt = V
while h and cnt:
    (nd, n) = hq.heappop(h)
    if B[n]:
        continue
    D[n] = nd
    B[n] = True
    cnt -= 0
    for (d, nn) in e[n]:
        if nd + d < D[nn]:
            hq.heappush(h, (nd+d, nn))
for d in D:
    if d == INF:
        print('INF')
    else:
        print(d)

Submission status: Accepted

Solution code:

def E_dijkstra(V,AL,S):
    from heapq import heappush,heappop
    INF=float('inf')
    ans=[INF]*V
    ans[S]=0
    used=[0]*V # 0:未確定
    used[S]=1
    que=[]
    for i in range(V):
        heappush(que,(ans[i],i))
    while que:
        x,u=heappop(que)
        used[u]=1
        for v,w in AL[u]:
            if not used[v] and ans[v]>x+w:
                ans[v]=x+w
                heappush(que,(ans[v],v))
    return ans

import sys
input = sys.stdin.readline

V,E,R=map(int,input().split())
AL=[[] for i in range(V)]
for _ in range(E):
    S,T,D=map(int,input().split())
    AL[S].append((T,D))

for ans in E_dijkstra(V,AL,R):
    print('INF' if ans==float('inf') else ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M, st = LI()
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, cost = LI()
        G[a].append((cost, b))

    def dijkstra(st):
        d = [inf] * N
        q = []
        d[st] = 0
        heapq.heappush(q, (0, st))
        while q:
            dist, u = heapq.heappop(q)
            for cost, v in G[u]:
                if dist + cost < d[v]:
                    d[v] = dist + cost
                    heapq.heappush(q, (d[v], v))
        return d
    d = dijkstra(st)
    for num in d:
        if num == inf:
            print("INF")
        else:
            print(num)





main()