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:
#!usr/bin/env python3

'''This method compute single source shortest path and then out put the costs 
to reach each nodes.

|V| |E| r
s_0 t_0
...
s_|E|-1 t_|E|-1

Constraints
    1 ??? |V| ??? 100000
    0 ??? di ??? 10000
    0 ??? |E| ??? 500000
    There are no parallel edges
    There are no self-loops

Example

Input:
4 5 
0 1 
0 2 
1 2 
2 3 
1 3 

Output:
0
1
3
4
'''

from collections import defaultdict

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    d = {}
    INF = 20000
    for i in range(V):
        d[i] = INF
    #print(d)
    d[0] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + 1:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])

    for k in d.keys():
        if d[k] > 10000:
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

from collections import defaultdict

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    d = {}
    INF = 20000
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + 1:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])

    for k in d.keys():
        if d[k] > 10000:
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3

'''This method compute single source shortest path and then out put the costs 
to reach each nodes.

|V| |E| r
s_0 t_0
...
s_|E|-1 t_|E|-1

Constraints
    1 ??? |V| ??? 100000
    0 ??? di ??? 10000
    0 ??? |E| ??? 500000
    There are no parallel edges
    There are no self-loops

Example

Input:
4 5 
0 1 
0 2 
1 2 
2 3 
1 3 

Output:
0
1
3
4
'''

from collections import defaultdict

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    d = {}
    INF = 200000
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + 1:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])

    for k in d.keys():
        if d[k] > 10000:
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
print "aho"

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    d = {}
    INF = float('inf')
    #INF = 20000
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])

    for k in d.keys():
        if d[k] > 10000:
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    d = {}
    #INF = float('inf')
    INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])

    for k in d.keys():
        if d[k] > 10000:
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = heappop(q)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                heappush(q, v[0])

    #for k in d.keys():
    #    if d[k] == float('inf'):
    #        print("INF")
    #    else:
    #        print(d[k])

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#from collections import defaultdict

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]

    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])

    for k in d.keys():
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
import time

def main():
    #Read stdin

    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))
    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([R])
    while q:

        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]

                q.append(v[0])

    for k in range(V):
        if d[k] == float('inf'):
            
            print("INF")
        else:
            print(d[k])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque


def main():
    #Read stdin

    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))
    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([R])
    while q:

        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]

                q.append(v[0])

    for k in range(V):
        if d[k] == float('inf'):
            
            print("INF")
        else:
            print(d[k])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque


def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))
    #initialized
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([R])
    while q:
        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])

    for k in range(V):
        if d[k] == float('inf'):
            
            print("INF")
        else:
            print(d[k])

Submission status: Wrong Answer

Solution code:

from collections import defaultdict
from collections import deque
# import time

def main():
    # Read stdin
    # start = time.clock()
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    # Adjacency list
    G = defaultdict(list)
    for i in range(E):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t, w))
    # initialized
    d = {}
    INF = float('inf')
    # INF = 10001
    #for i in range(V):
    #    d[i] = INF
    d[R] = 0
    # deque is better than list aka double link list O(1) for pop head and append
    q = deque([(R)])
    seen = set([])
    while q:
        # u = heappop(q)
        u = q.popleft()
        if u not in seen:
            seen.add(u)
            for v in G[u]:
                if v[0] not in seen:
                    if v[0] in d.keys():
                        if d[v[0]] > d[u] + v[1]:
                            d[v[0]] = d[u] + v[1]
                    else:
                        d[v[0]] = d[u] + v[1]
                        q.append(v[0])



    for k in range(V):
        if k not in d.keys():
            print("INF")
        else:
            print(d[k])
    # end = time.clock() - start
    # print('Computation time : {}'.format(end))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from sys import stdin


def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([(R)])
    while q:
        # u = heappop(q)
        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                # heappush(q, v[0])
                q.append(v[0])
    for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])


V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict(list)
for case in range(1,1+V):
    (s, t, w) = tuple(int(x) for x in stdin.readline().split())
    G[s].append((t,w))
sp(G, R, V)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from sys import stdin

def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([(R)])
    while q:
        # u = heappop(q)
        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                # heappush(q, v[0])
                q.append(v[0])
    return d


V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict(list)
for case in range(1,1+V):
    (s, t, w) = tuple(int(x) for x in stdin.readline().split())
    G[s].append((t,w))
d = sp(G, R, V)
for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from sys import stdin

def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([(R)])
    while q:
        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])
    return d


V, E, R = tuple(int(x) for x in stdin.readline().split(' '))
G = defaultdict(list)
for case in range(E):
    s, t, w = tuple(int(x) for x in stdin.readline().split(' '))
    G[s].append((t,w))
print(G)
d = sp(G, R, V)
for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = [[] for n in range(vertice)]
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().split(" "))
    link[i].append(j)
    weight[i].update({j:w})
#print(weight,link)
for v in range(vertice):
    goal = v
    queue = []
    heapq.heappush(queue,[0,source])
    went = set()

    while queue != []:
        #print(queue)
        now_cost,here = heapq.heappop(queue)
        #print(now_cost,here,queue)
        if here == goal:
            print(now_cost)
            break

        can_go = link[here]
        not_went = set(can_go) - went
        #print(v,here,now_cost,not_went,queue)
        for nw in not_went:
            next_cost = now_cost + weight[here][nw]
            heapq.heappush(queue,(next_cost,nw))
        went = went | {here}
        queue.sort(key=lambda x:x[1],reverse=True)
    else:
        print("INF")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq


def aaa():
    with open("input.txt","r") as f:
        vertice,edge,source = map(int,f.readline().split(" "))
        link = defaultdict(dict)
        weight = defaultdict(dict)
        for e in range(edge):
            i,j,w = map(int,f.readline().split(" "))
            link[i] = link.get(i,set()) | {j}
            weight[i].update({j:w})
        #print(weight,link)
        for v in range(vertice):
            goal = v
            queue = []
            heapq.heappush(queue,(0,source))
            heapq.heapify(queue)
            went = {n:0 for n in range(vertice)}

            while queue != []:
                #print(queue)
                now_cost,here = heapq.heappop(queue)
                #print(now_cost,here,queue)
                if here == goal:
                    print(now_cost)
                    break
                elif went[here]:
                    continue
                can_go = link[here]

                #print(v,here,now_cost,not_went,queue)
                for nw in can_go:
                    if went[nw]:
                        continue
                    next_cost = now_cost + weight[here][nw]
                    heapq.heappush(queue,(next_cost,nw))
                went[here] = 1
            else:
                print("INF")

Submission status: Wrong Answer

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

def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    q = [(0, R)]
    d[R] = 0
    heapify(q)
    while q:
        (cost, v) = heappop(q)
        for (next, c) in G[v].items():
            if 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: Wrong Answer

Solution code:
from heapq import heappush, heappop
V, E, r = map(int, input().split())
inf = 10**10
edges = [[] for _ in [None]*V]
vertices = [inf]*V
vertices[r] = 0

for _ in [None]*E:
    s, t, d = map(int, input().split())
    edges[s].append((t,d))

q = [(0, r)]
rem = V - 1
while q and rem:
    cost, v = heappop(q)
    for dest, _cost in edges[v]:
        newcost = cost + _cost
        if vertices[dest] > newcost:
            vertices[dest] = newcost
            heappush(q, (newcost, dest))
            rem -= 1

print("\n".join([str(n) if n!=inf else "INF" for n in vertices]))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
V, E, r = map(int, input().split())
inf = 10**10
edges = [[] for _ in [None]*V]
vertices = [inf]*V
vertices[r] = 0

for _ in [None]*E:
    s, t, d = map(int, input().split())
    edges[s].append((t,d))

q = [(0, r)]
rem = V
while q and rem:
    rem -= 1
    cost, v = heappop(q)
    for dest, _cost in edges[v]:
        newcost = cost + _cost
        if vertices[dest] > newcost:
            vertices[dest] = newcost
            heappush(q, (newcost, dest))

print("\n".join([str(n) if n!=inf else "INF" for n in vertices]))

Submission status: Wrong Answer

Solution code:
import heapq


def main():
    nvertices, nedges, s = map(int, input().split())
    adj = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))

    INF = float('inf')
    costs = [INF] * nvertices
    costs[0] = 0
    que = [(0, s)]
    for i in range(1, nvertices):
        que.append((INF, 1))
    while que:
        cost, u = heapq.heappop(que)
        if cost > costs[u]:
            continue
        costs[u] = cost
        for v, w in adj[u]:
            if costs[v] > costs[u] + w:
                costs[v] = costs[u] + w
                heapq.heappush(que, (costs[v], v))

    for i in range(nvertices):
        print(costs[i] if costs[i] < INF else "INF")


main()

Submission status: Wrong Answer

Solution code:
v, e, r = list(map(int, input().split()))
edgeList = [[0, 0, 0] for i in range(e)]
for i in range(e):
    a = list(map(int, input().split()))
    edgeList[i] = [a[2], a[0], a[1]]
 
 
rootList = [-1 for i in range(v)]
parent = [0 for i in range(v)]
lenList = [float("inf") for i in range(v)]
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)

Submission status: Wrong Answer

Solution code:
v,e,s=map(eval,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

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

dis[s]=0

for i in range(v):
    for (t,d) in edge[i]:
        if dis[t]>dis[i]+d:
            dis[t]=dis[i]+d

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

Submission status: Wrong Answer

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(finished<v and not q.empty()):
    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: Wrong Answer

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(finished<=v and not q.empty()):
    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: Wrong Answer

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(finished<v and not q.empty()):
    now=q.get()
#    print("get",now)
    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+=1       
#            print("put",(dis[vt],vt))

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

Submission status: Wrong Answer

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

    
main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop