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: Wrong Answer

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])
    print(1)
    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: Wrong Answer

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)
    for i in range(V-len(edgeset)):
        edgeset.append([])

    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[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])
            
    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: Wrong Answer

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)):
	print(w[i])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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])

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: Wrong Answer

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):
    [e1, e2, c] = list(map(int, input("").split()))
    if int(e1) == r:
        dict_r[(e1, e2)] = int(c)
    else:
        dict_c[(e1, e2)] = int(c)

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: Wrong Answer

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):
    [e1, e2, c] = list(map(int, input("").split()))
    if e1 == r:
        dict_r[(e1, e2)] = c
    else:
        dict_c[(e1, e2)] = c

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(str(0))
    elif dict_r[(r, i)] == infty:
        print("INF")
    else:
        print(str(dict_r[(r, i)]))

Submission status: Wrong Answer

Solution code:
import sys;


class MinTree:
    class Cell:
        def __init__(self):
            self.value = 99999999999999
            self.right = None
            self.left = None
            self.parent = None

    def __init__(self):
        self.top = self.Cell()
        self.cell = self.Cell()
        self.cell.parent = self.top
        self.top.left = self.cell

    def insert(self, value, cell):
        if(cell.value == 99999999999999):
            cell.value = value
        else:
            cell = self.find(cell)
            if(cell.left == None):
                cell.left = self.Cell()
                cell.left.parent = cell
                cell.left.value = value
                while(True):
                    if(cell.value > cell.left.value):
                        if(cell.parent.right == cell):
                            cell.parent.right = cell.left
                        else:
                            cell.parent.left = cell.left
                        cell,cell.left = self.replace(cell,cell.left)
                    else:
                        break
            elif(cell.right == None):
                cell.right = self.Cell()
                cell.right.parent = cell
                cell.right.value = value
                while(True):
                    if(cell.value > cell.right.value):
                        if(cell.parent.right == cell):
                            cell.parent.right = cell.right
                        else:
                            cell.parent.left = cell.right
                        cell,cell.right = self.replace(cell,cell.right)
                    else:
                        break

    def replace(self,cell1,cell2):
        swap = self.Cell()
        swap.value = cell1.value
        swap.left = cell1.left
        swap.right = cell1.right
        swap.parent = cell1.parent
        cell1.value = cell2.value
        cell1.left = cell2.left
        cell1.right = cell2.right
        cell1.parent = cell2.parent
        cell2.value = swap.value
        cell2.left = swap.left
        cell2.right = swap.right
        cell2.parent = swap.parent

        return cell1,cell2

    def printTree(self,cell):
        if(cell.left != None):
            self.printTree(cell.left)
        print(cell.value)
        if(cell.right != None):
            self.printTree(cell.right)

    def find(self,cell):
        if(cell.left == None):
            return cell
        else:
            return self.find(cell.left)

        if(cell.right == None):
            return cell
        else:
            return self.find(cell.right)



def dfs(u,s,target, route=None):
    if(route == None):
        route=[]
    if(u in route):
        return
    route.append(u)
    global heap
    if(route[len(route)-1] == target):
        heap.insert(s,heap.top.left)
        return
    for j in range(e):
        if(e_1[j] == u):
            if(vs[e_2[j]] == 0):
                s += e_w[j]
                dfs(e_2[j],s,target,route)


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

vs=[0]*v;

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

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

for i in range(v):
    heap = MinTree()
    dfs(r,0,i)
    if(heap.top.left.value != 99999999999999):
        print(heap.top.left.value)
    else:
        print("INF")

Submission status: Wrong Answer

Solution code:
import sys
import heapq


def dfs(u,s,target, route=None):
    if(route == None):
        route=[]
    route.append(u)
    global h
    if(u == target):
        heapq.heappush(h,s)
        return
    for j in range(e):
        if(e_1[j] == u):
            if e_2[j] not in route[0:len(route)-1]:
                
                s = s + e_w[j]
                dfs(e_2[j],s,target,route[0:])


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

vs=[0]*v;

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

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

for i in range(v):
    h = []
    dfs(r,0,i)
    if(len(h) != 0):
        print(heapq.heappop(h))
    else:
        print("INF")

Submission status: Wrong Answer

Solution code:
import sys
import heapq


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


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

vs=[0]*v;

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

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

for i in range(v):
    h = []
    dfs(r,0,i)
    if(len(h) != 0):
        print(heapq.heappop(h))
    else:
        print("INF")

Submission status: Wrong Answer

Solution code:
# Single Source Shortest Path
class node():
    def __init__(self, v, cost):
        self.v = v
        self.cost = cost

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

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

def min_heap(i):
    global root_c
    l = 2*i
    r = 2*i + 1
    if l <= len(root_c) - 1 and root_c[l].cost < root_c[i].cost:
        min = l
    else:
        min = i
    if r <= len(root_c) - 1 and root_c[r].cost < root_c[min].cost:
        min = r
    if min != i:
        root_c[i], root_c[min] = root_c[min], root_c[i]
        min_heap(min)

def extract_min():
    global root_c
    min = root_c[1]
    root_c[1] = root_c[len(root_c) - 1]
    del root_c[len(root_c) - 1]
    min_heap(1)
    return min

def decrease_key(v, c):
    global root_c
    root_c[v].cost = c
    while v > 1 and root_c[int(v/2)].cost > root_c[v].cost:
        root_c[int(v/2)], root_c[v] = root_c[v], root_c[int(v/2)]
        v = int(v/2)

def min_insert(v, c):
    global infty, root_c
    for i in range(len(root_c)):
        if root_c[i].v == v:
            decrease_key(i,c)
            return

    root_c.append(node(v, infty))
    decrease_key(len(root_c) - 1, c)

def Dijkstra(root, n):
    global infty, dict_c, root_c, final_c
    label = [i for i in range(n)]
    del label[root]

    while len(label) != 0:

        if len(root_c) > 1:
            min_node = extract_min()
        else:
            break

        final_c[min_node.v] = min_node.cost
        for i in range(len(label)):
            if min_node.v == label[i]:
                delete_label = i
                continue

            if ((min_node.v, label[i]) in dict_c.keys()) == True:
                if final_c[label[i]] > final_c[min_node.v] + dict_c[(min_node.v, label[i])]:
                    final_c[label[i]] = final_c[min_node.v] + dict_c[(min_node.v, label[i])]
                    min_insert(label[i], final_c[label[i]])
        del label[delete_label]

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

Submission status: Wrong Answer

Solution code:

nv,ne, r = [int(i) for i in input().split()]

g = [[] for i in range(nv)]


for i in range(ne):
    s,t,d = [int(j) for j in input().split()]
    g[s].append([t,d])

shortest = [0 for i in range(nv)]
visited = [False for i in range(nv)]

def pursue_from(index):
    for next_index, weight in g[index]:
        total = shortest[index] + weight
        if  visited[next_index] == False or shortest[next_index] > total:
            visited[next_index] = True
            shortest[next_index] = total
            pursue_from(next_index)

visited[r] = True
pursue_from(r)

for i in range(nv):
    if visited[i] == False:
        print("INF")
        break
    print(shortest[i])

Submission status: Wrong Answer

Solution code:

nv,ne, r = [int(i) for i in input().split()]

g = [[] for i in range(nv)]


for i in range(ne):
    s,t,d = [int(j) for j in input().split()]
    g[s].append([t,d])

costs = [-1 for i in range(nv)]

def pursue_from(index):
    for next_index, weight in g[index]:
        total = costs[index] + weight
        if  costs[next_index] == -1:
            costs[next_index] = total
            pursue_from(next_index)

costs[r] = 0
pursue_from(r)

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

Submission status: Wrong Answer

Solution code:
import heapq
from enum import Enum, auto

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

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.WHITE for i in range(V)]
    d = [float('inf') for i in range(V)]
    d[s] = 0

    pqueue = [s]
    while len(pqueue) >= 1:
        u = heapq.heappop(pqueue)
        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, v)

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

Submission status: Wrong Answer

Solution code:
n,e,r = map(int,raw_input().split())

inf = float("inf")
distances = [inf for i in range(n)]
distances[r] = 0
costs = [[-1 for i in range(n)] for j in range(n)]
parent = [-1 for i in range(n)]
color = ['white' for i in range(n)]

for i in range(e):
	s,t,c = map(int,raw_input().split())

	costs[s][t] = c

while True:
	mincost = inf
	u = 0
	for i in range(n):
		if color[i] != 'black' and distances[i] < mincost:
			mincost = distances[i]
			u = i

	if mincost == inf :
		break

	color[u] = 'black'

	for v in range(n):
		if color[v] != 'black' and costs[u][v] > 0:
			if distances[u] + costs[u][v] < distances[v]:
				distances[v] = distances[u] + costs[u][v]
				parent[v] = u
				color[v] = 'gray'


for i in range(n):
	if distances[i] != inf:
		print distances[i]
	else :
		print 'INF'