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: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappush, heappop, heapify
from sys import stdin
#import time

def sp(G,R,V):
    d = {}
    q = [(0, R)]
    d[R] = 0
    heapify(q)
    while q:
        (cost, v) = heappop(q)
        for (next, c) in G[v].items():
            if v not in d:
                d[v] = c
            elif d[next] > d[v] + c:
                d[next] = d[v] + c
                heappush(q, (d[next], next))
    return d

#start = time.clock()

V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict(dict)
for case in range(E):
    s, t, w = [int(x) for x in stdin
    .readline().split()]
    G[s][t] = w
d = sp(G, R, V)
for k in range(V):
    if k not in d:
        print("INF")
    else:
        print(d[k])
#print('Computation time : {}'.format(time.clock()-start))

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappush, heappop

inf = 1<<30

def solve():
    N, M, s = map(int, sys.stdin.readline().split())
    Adj = [[] for i in range(N)]

    for i in range(M):
        ui, vi, ci = map(int, sys.stdin.readline().split())
        Adj[ui].append((vi, ci))

    d = dijkstra(N, Adj, s)

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

def dijkstra(N, Adj, s):
    d = [inf] * N
    d[s] = 0
    pq = [(0, s)]

    for i in range(N - 1):
        while 1:
            di, v = heappop(pq)

            if di == d[v]:
                break

        for u, c in Adj[v]:
            if d[v] + c < d[u]:
                d[u] = d[v] + c
                heappush(pq, (d[u], u))

    return d

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
v, e, r = list(map(int, input().split()))
edgeList = [[0, 0, 0] for i in range(e)]
rootList = [-1 for i in range(v)]
parent = [-1 for i in range(v)]
lenList = [0 for i in range(v)]

for i in range(e):
    a = list(map(int, input().split()))
    edgeList[e] = [a[2], a[0], a[1]]
 
 
rootList = [-1 for i in range(n)]
parent = [0 for i in range(n)]
lenList = [float("inf") for i in range(n)]
lenList[r] = 0
def getRoot(x):
    root = rootList[x]
    if root < 0:
        rootList[x] = x
    elif root != x:
        rootList[x] = getRoot(root)
    return rootList[x]
 
flag = True
while flag:
    flag = False
    edgeList.sort(key=lambda x: (x[0] + lenList[x[1]]))
    for e in edgeList:    # weight:e[0], e[1]->e[2]
        if e[2] == 0:
            continue
        x = getRoot(e[1])
        y = getRoot(e[2])
        if x == r != y:
            parent[e[2]] = e[1]
            lenList[e[2]] = lenList[e[1]] + e[0]
            rootList[y] = r
            flag = True
            break
 
for i in lenList:
    if i == float("inf"):
        print("INF")
    else:
        print(i, j)

Submission status: Runtime Error

Solution code:
'''
????????£????????????????????????

'''

import queue
v,e,s=map(int,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(int,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

q = queue.PriorityQueue()
q.put((0,s))
finished=0

while(not finished==v):
    now=q.get()
#    print("get",now)
    nowv=now[1]
    finished+=1
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
            
#            print("put",(dis[vt],vt))

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

Submission status: Runtime Error

Solution code:
'''
????????£????????????????????????

'''

import queue
v,e,s=map(int,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(int,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

q = queue.PriorityQueue()
q.put((0,s))

'''
while(not q.empty()):
    now=q.get()

    nowv=now[1]
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
'''
finished=0
while(finished<v and not q.empty()):
    now=q.get()
    nowv=now[1]
    if now[0]>dis[nowv] continue;
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
    finished+=1       

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

Submission status: Runtime Error

Solution code:
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'''

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

    setS.append(r)
    setV[0][0]=0
    setV[0][1]=-1
    setdist[r]=0
    setV=binary_heap_building(setV)
    '''initiating data'''

    for i in range(V-1):
        nowvert=setS[-1]
        '''the on process vertices'''
        for j in range(len(edgeset)):
            if(nowvert==edgeset[j][0]):
                '''try to find all the linkage of this on process vertices'''
                newdist=edgeset[j][2]+setdist[nowvert]
                olddist=setdist[edgeset[j][1]]
                '''calculating the new distance including the on process vertices'''
                if(newdist<olddist):
                    setdist[edgeset[j][1]]=newdist
                    setV=binary_heap_change(setV,newdist,edgeset[j][1])
                '''making comparision to determin which to stay'''
        
        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_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):
    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

    
main()

Submission status: Runtime Error

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)
edges.sort()
w = Dijkstra(V,edges,r)
for i in range(len(w)):
	print(w[i])

Submission status: Runtime Error

Solution code:
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    return d
'''
result = Dijkstra(r, vertex)
for i in range(vertex):
    if i == r:
        result[i] = 0
    if result[i] == infty:
        result[i] = "INF"
    print(result[i])

Submission status: Runtime Error

Solution code:
from memory_profiler import profile
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

@profile
def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    del visited_order
    del label
    del D
    del min_cost

    d[root] = 0
    return d

result = Dijkstra(r, vertex)

for i in range(vertex):
    if result[i] == infty:
        result[i] = "INF"
    print(result[i])

Submission status: Runtime Error

Solution code:
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    del visited_order
    del label
    del D
    del min_cost

    d[root] = 0
    return d

result = Dijkstra(r, vertex)

for i in range(vertex):
    if result[i] == infty:
        result[i] = "INF"
    print(result[i])

Submission status: Runtime Error

Solution code:
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
dict_r = {}
for i in range(vertex):
    dict_r[(r,i)] = infty

dict_c = {}
for i in range(edge):
    data = list(map(int, input("").split()))
    if int(data[0]) == r:
        dict_r[(data[0],data[1])] = int(data[2])
    else:
        dict_c[(data[0],data[1])] = int(data[2])
del data

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global dict_r, dict_c, infty
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > dict_r[(root, i)]:
                min_cost = dict_r[(root, i)]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if ((min_node, i) in dict_c.keys()) == True:
                if dict_r[(root, i)] > dict_r[(root, min_node)] + dict_c[(min_node, i)]:
                    dict_r[(root, i)] = dict_r[(root, min_node)] + dict_c[(min_node, i)]

Dijkstra(r, vertex)

for i in range(vertex):
    if r == i:
        print(0)
    elif dict_r[(r, i)] == infty:
        print("INF")
    else:
        print(dict_r[(r, i)])

Submission status: Runtime Error

Solution code:
import sys
import heapq


def dfs(u,s,target, vs):
    vs[u] = 1
    if(u == target):
        global h
        heapq.heappush(h,s)
        return
    for j in range(e):
        if(e_1[j] == u):
            if(vs[e_2[j]] != 1):
                count = s + e_w[j]
                print(s,e_2[j],vs)
                dfs(e_2[j],count,target,vs[0:])

def dijsktra(start, v, e):
    d = [0]*v
    prev = [0]*v
    v_q=[[] for i in range(v)];

    INF = 9999999999999999999
    for u in range(v):
        if(u != start):
            d[u] = INF
        else:
            d[u] = 0 
        prev[u] = -1
        heapq.heappush(v_q[u],d[u])

    

    while(True):
        min = INF
        for i in range(len(v_q)):
            if(len(v_q[i]) != 0):
                if(min > v_q[i][0]):
                    min = v_q[i][0]
                    u = i
        heapq.heappop(v_q[u])
        if(min == (INF)):
            break
        for j in range(e):
            if(u == e_1[j]):
                alt = d[u]+e_w[j]
                if(d[e_2[j]] > alt):
                    d[e_2[j]] = alt
                    prev[e_2[j]] = u
                    heapq.heappush(v_q[e_2[j]],alt)

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

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

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(e):
    e_1[i], e_2[i], e_w[i] = map(int, input().split());

dijsktra(r,v,e)

Submission status: Runtime Error

Solution code:
import sys
import heapq


def dfs(u,s,target, vs):
    vs[u] = 1
    if(u == target):
        global h
        heapq.heappush(h,s)
        return
    for j in range(e):
        if(e_1[j] == u):
            if(vs[e_2[j]] != 1):
                count = s + e_w[j]
                print(s,e_2[j],vs)
                dfs(e_2[j],count,target,vs[0:])

def dijsktra(start, v, e):
    d = [0]*v
    prev = [0]*v
    v_q=[[] for i in range(v)];

    INF = 9999999999999999999
    for u in range(v):
        if(u != start):
            d[u] = INF
        else:
            d[u] = 0 
        prev[u] = -1
        heapq.heappush(v_q[u],d[u])

    

    while(True):
        min = INF
        u = -1
        for i in range(len(v_q)):
            if(len(v_q[i]) != 0):
                if(min > v_q[i][0]):
                    min = v_q[i][0]
                    u = i
        if(u!=-1):
            heapq.heappop(v_q[u])
         if(min == (INF)):
            break
        for j in range(e):
            if(u == e_1[j]):
                alt = d[u]+e_w[j]
                if(d[e_2[j]] > alt):
                    d[e_2[j]] = alt
                    prev[e_2[j]] = u
                    heapq.heappush(v_q[e_2[j]],alt)

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

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

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(e):
    e_1[i], e_2[i], e_w[i] = map(int, input().split());

dijsktra(r,v,e)

Submission status: Runtime Error

Solution code:
import sys
import heapq


def dfs(u,s,target, vs):
    vs[u] = 1
    if(u == target):
        global h
        heapq.heappush(h,s)
        return
    for j in range(e):
        if(e_1[j] == u):
            if(vs[e_2[j]] != 1):
                count = s + e_w[j]
                print(s,e_2[j],vs)
                dfs(e_2[j],count,target,vs[0:])

def dijsktra(start, v, e):
    d = [0]*v
    prev = [0]*v
    v_q=[];

    INF = 9999999999999999999
    for u in range(v):
        if(u != start):
            d[u] = INF
        else:
            d[u] = 0 
        prev[u] = -1

    heapq.heappush(v_q,(0,start))
    heapq.heappush(v_q,(INF,0))
    

    while(True):
        cost,u = heapq.heappop(v_q)
        if(cost > d[u]):
            continue
        if(cost == INF):
            break
        for j in range(e):
            if(u == e_1[j]):
                alt = d[u]+e_w[j]
                if(d[e_2[j]] > alt):
                    d[e_2[j]] = alt
                    prev[e_2[j]] = u
                    heapq.heappush(v_q,(alt,e_2[j]))
    for i in range(v):
        if(d[i] != INF):
            print(d[i])
        else:
            print("INF")

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

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(e):
    e_1[i], e_2[i], e_w[i] = map(int, input().split());

dijsktra(r,v,e)

Submission status: Runtime Error

Solution code:
INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
heapq.heappush(v_q,(0,r))
while(len(v_q) != 0):
    cost,u = heapq.heappop(v_q)
    if(cost > d[u]):
        continue
    for j in range(e):
        if(u == e_1[j]):
            alt = cost+e_w[j]
            if(d[e_2[j]] > alt):
                d[e_2[j]] = alt
                heapq.heappush(v_q,(alt,e_2[j]))

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

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

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

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(e):
    e_1[i], e_2[i], e_w[i] = map(int, input().split());

v_q=[];

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
heapq.heappush(v_q,(0,r))
while(len(v_q) != 0):
    cost,u = heapq.heappop(v_q)
    if(cost > d[u]):
        continue
    for j in range(e):
        if(u == e_1[j]):
            alt = cost+e_w[j]
            if(d[e_2[j]] > alt):
                d[e_2[j]] = alt
                heapq.heappush(v_q,(alt,e_2[j]))

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

Submission status: Runtime Error

Solution code:
import sys
from heapq

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

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(e):
    e_1[i], e_2[i], e_w[i] = map(int, input().split());

v_q=[];

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
heapq.heappush(v_q,(0,r))
while(len(v_q) != 0):
    cost,u = heapq.heappop(v_q)
    if(cost > d[u]):
        continue
    for j in range(e):
        if(u == e_1[j]):
            alt = cost+e_w[j]
            if(d[e_2[j]] > alt):
                d[e_2[j]] = alt
                heapq.heappush(v_q,(alt,e_2[j]))

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

Submission status: Runtime Error

Solution code:
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,d = x
        if d[t] > d[s] + d:
            count += 1
            d[t] = d[s] + d
    if count == 0:
        break

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

Submission status: WA: Presentation Error

Solution code:
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)])

    setS=[]
    setV=[i for i in range(V)]
    setdist=[500000*10000+1 for i in range(V)]

    setS.append(r)
    setV.pop(r)
    setdist[r]=0

    for i in range(V-1):
        nowvert=setS[-1]
        for j in range(len(edgeset)):
            if(nowvert==edgeset[j][0]):
                newdist=edgeset[j][2]+setdist[nowvert]
                olddist=setdist[edgeset[j][1]]
                if(newdist<olddist):
                    setdist[edgeset[j][1]]=newdist
        setVdist=[setdist[setV[k]] for k in range(len(setV))]
        position=setVdist.index(min(setVdist))
        setS.append(setV[position])
        setV.pop(position)
                    
    for i in range(V):
        if(setdist[i]==500000*10000+1):
            print('INF')
        else:
            print(setdist[i])
        print('\n')
    
    return 0

main()