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: Time Limit Exceeded

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'''


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

    group.append(r)
    setdist[r]=0
    '''initiating data'''


    for i in range(9999999):
        
        if(len(group)==0):
            break

        nowvert=group[0]
        group.pop(0)
        for j in range(len(edgeset)):
            if(nowvert==edgeset[j][0]):
                newdist=edgeset[j][2]+setdist[edgeset[j][0]]
                '''new distance is computed by the original distance of the source of a edge plus the edge distance itself'''
                olddist=setdist[edgeset[j][1]]
                '''old distance is the original distance of the target of a edge'''
                if(newdist<olddist):
                    setdist[edgeset[j][1]]=newdist
                    group.append(edgeset[j][1])
                    '''choose the smaller distance. and if it become smaller,make it in the group'''
                    
            
            

                    
    for i in range(V):
        if(setdist[i]==500000*10000+1):
            print('INF')
        else:
            print(setdist[i])
    '''data output'''
    
    return 0

main()

Submission status: Time Limit Exceeded

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[r][0]=r
    setV[r][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: Time Limit Exceeded

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'''

    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([0,0])
    setdist[r]=0
    setV=binary_heap_building(setV)
    '''initiating data'''

    for i in range(9999999999):
        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_add(setV,newdist,edgeset[j][1])
                '''making comparision to determin which to stay'''
        if(setV==[[0,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_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: Time Limit Exceeded

Solution code:
import sys
from collections import deque

# 初期化
n_V, n_E, r = map(int, input().split())

E = [[] for _ in range(n_V)]
D = [sys.maxsize for _ in range(n_V)]

# 入力
for i in range(n_E):
    v, e, d = map(int, input().split())
    E[v].append((e, d))

#　各頂点への最短距離を求める処理
D[r] = 0
queue = deque([r])
visited = set()

while len(queue) != 0:
    current = queue.popleft()
    visited.add(current)

    for e, d in E[current]:
        if D[e] > D[current] + d:
            D[e] = D[current] + d
            if e in visited: visited.remove(e)

        if e not in queue and e not in visited:
            queue.append(e)

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

Submission status: Time Limit Exceeded

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]
                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: Time Limit Exceeded

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]
                dfs(e_2[j],count,target,vs[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,vs)
    if(len(h) != 0):
        print(heapq.heappop(h))
    else:
        print("INF")

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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 == 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: Time Limit Exceeded

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 == INF):
            break
        if(cost > d[u]):
            continue
        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: Time Limit Exceeded

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



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))
heapq.heappush(v_q,(INF,0))
while(True):
    cost,u = heapq.heappop(v_q)
    if(cost == INF):
        break
    if(cost > d[u]):
        continue
    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
                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: Time Limit Exceeded

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



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))
heapq.heappush(v_q,(INF,0))
while(True):
    cost,u = heapq.heappop(v_q)
    if(cost == INF):
        break
    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: Time Limit Exceeded

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



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: Time Limit Exceeded

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))
        final_c[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:
        if root_c[l].cost < root_c[i].cost:
            min = l
        elif root_c[l].v < root_c[i].v:
            min = l
        else:
            min = i
    else:
        min = i
    if r <= len(root_c) - 1 and root_c[r].cost <= root_c[min].cost:
        if root_c[r].cost < root_c[min].cost:
            min = r
        elif root_c[r].v < root_c[min].v:
            min = r
        #else:

    if min != i:
        root_c[i], root_c[min] = root_c[min], root_c[i]
        min_heap(min)

def build_min_heap():
    global root_c
    length = len(root_c) - 1
    for i in range(int(length/2), 0, -1):
        min_heap(i)

def extract_min():
    global root_c
    min = root_c[1]

    #print("min_cost  ", root_c[1].cost, root_c[2].cost, root_c[3].cost, root_c[4].cost, root_c[5].cost, root_c[6].cost, root_c[7].cost)
    #print("min_vertex", root_c[1].v, root_c[2].v, root_c[3].v, root_c[4].v, root_c[5].v, root_c[6].v, root_c[7].v)

    root_c[1] = root_c[len(root_c) - 1]

    #print("1: ",root_c[1].cost, root_c[1].v)

    del root_c[len(root_c) - 1]
    min_heap(1)

    #print("min_cost  2", root_c[1].cost, root_c[2].cost, root_c[3].cost, root_c[4].cost, root_c[5].cost, root_c[6].cost)
    #print("min_vertex2", root_c[1].v, root_c[2].v, root_c[3].v, root_c[4].v, root_c[5].v, root_c[6].v)
    #print("length: ",len(root_c))

    return min

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

def min_insert(v, c):
    global infty, root_c
    for i in range(1, 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):

    count = 1

    global infty, dict_c, root_c, final_c
    label = [i for i in range(n)]

    #print(count, label[root], final_c[label[root]])
    count += 1

    del label[root]

    while len(label) != 0:
        if len(root_c) > 1:
            min_node = extract_min()
        else:
            break

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

        #print(count, label[delete_label], final_c[label[delete_label]])
        count += 1

        del label[delete_label]

build_min_heap()

'''
print("root_c :")
for i in range(len(root_c)):
    print(root_c[i].cost)
print("\n")
'''

Dijkstra(r, vertex)

#print("\n")

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

Submission status: Time Limit Exceeded

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

edges = [map(int,raw_input().split()) for i in range(e)]

inf = float('inf')
distance = [inf for i in range(v)]

distance[r] = 0

for dist in distance:
	for edge in edges:
		if distance[edge[0]] != inf and distance[edge[1]] > distance[edge[0]] + edge[2]:
			distance[edge[1]] = distance[edge[0]] + edge[2]

for dist in distance:
	if dist == inf :
		print 'INF'
	else:
		print dist

Submission status: Time Limit Exceeded

Solution code:
import sys
import 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: Time Limit Exceeded

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=deque();

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

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

Submission status: Time Limit Exceeded

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

#edges = [[float('inf') for _ in range(V)] for _ in range(V)]
edges = []

for _ in range(E):
    tmp = [int(x) for x in input().split()]
    #edges[s][t] = d
    edges.append(tmp)

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

for _ in range(V-1):
    for x in edges:
        d[x[1]] = min(d[x[1]], d[x[0]] + x[2])

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

Submission status: Memory Limit Exceeded

Solution code:
import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        num = len(adj)
        dist = [float('inf') for i in range(num)]
        prev = [float('inf') for i in range(num)]

        dist[start] = 0
        q = []
        heapq.heappush(q, (0, start))
        
        while len(q) != 0:
            prov_const, src = heapq.heappop(q)

            if dist[src] < prov_const:
                continue

            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(q, (dist[dest], dest))
                    prev[dest] = src

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

if __name__ == '__main__':
    p_inf = float('inf')
    l = map(int, raw_input().split())
    V, E, r = l[0], l[1], l[2]
    
    adj = [[p_inf] * V for i in range(V)]
    for i in range(V):
        adj[i][i] = 0
    for i in range(E):
        l = map(int, raw_input().split())
        s, t, d = l[0], l[1], l[2]
        adj[s][t] = d
    
    d = Dijkstra()
    result = d.dijkstra(adj, r)
    for i in result:
        if i == p_inf:
            print 'INF'
        else:
            print i

Submission status: Memory Limit Exceeded

Solution code:
import heapq

l = input().split()
V = int(l[0])
E = int(l[1])
r = int(l[2])

graph = [[0 if i==j else -1  for j in range(V)] for i in range(V)] # [[source, target, cost]]
for i in range(E):
    l = input().split()
    graph[int(l[0])][int(l[1])] = int(l[2])

heap = [(0,r)]
dist = [float("inf") for _ in range(V)]
visited = [False for _ in range(V)]
while heap:
    pop = heapq.heappop(heap)
    if dist[pop[1]] < pop[0]:
        continue
    dist[pop[1]] = pop[0]
    edges = [(w,i) for (i,w) in enumerate(graph[pop[1]]) if i != pop[1] and w >= 0 and not visited[i]]
    for (weight, target) in edges:
        heapq.heappush(heap, (pop[0]+weight, target))

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

Submission status: Memory Limit Exceeded

Solution code:
import heapq

l = input().split()
V = int(l[0])
E = int(l[1])
r = int(l[2])

graph = [[0 if i==j else -1  for j in range(V)] for i in range(V)] # [[source, target, cost]]
for i in range(E):
    l = input().split()
    graph[int(l[0])][int(l[1])] = int(l[2])

heap = [(0,r)]
dist = [float("inf") for _ in range(V)]
while heap:
    pop = heapq.heappop(heap)
    if dist[pop[1]] < pop[0]:
        continue
    dist[pop[1]] = pop[0]
    edges = [(w,i) for (i,w) in enumerate(graph[pop[1]]) if i != pop[1] and w >= 0 and dist[i] == float("inf")]
    for (weight, target) in edges:
        heapq.heappush(heap, (pop[0]+weight, target))

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

Submission status: Memory Limit Exceeded

Solution code:
import heapq

l = input().split()
V = int(l[0])
E = int(l[1])
r = int(l[2])

graph = [[0 if i==j else -1  for j in range(V)] for i in range(V)] # [[source, target, cost]]
for i in range(E):
    l = input().split()
    graph[int(l[0])][int(l[1])] = int(l[2])

heap = [(0,r)]
dist = [float("inf") for _ in range(V)]
while heap:
    pop = heapq.heappop(heap)
    if dist[pop[1]] < pop[0]:
        continue
    dist[pop[1]] = pop[0]
    for (i,w) in enumerate(graph[pop[1]]):
        if i!= pop[1] and w >= 0 and dist[i] == float("inf"):
            heapq.heappush(heap, (pop[0]+w, i))

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

Submission status: Memory Limit Exceeded

Solution code:
#!/usr/bin/python3
from heapq import heappush, heappop

inf = float('inf')

def inf_matrix(n):
    return [[inf for i in range(n)] for j in range(n)]

def dijkstra(r, w):
    V = len(w)
    result = [inf] * V
    used = [False] * V
    q = []
    heappush(q, (0, r))

    while len(q) > 0:
        min_w, min_next = heappop(q)
        if used[min_next]:
            continue
        used[min_next] = True
        result[min_next] = min_w
        for nxt, weight in enumerate(w[min_next]):
            if result[nxt] <= min_w + weight:
                continue
            heappush(q, (min_w + weight, nxt))

    return result


def main():
    V, E, r = map(int, input().split())
    w = inf_matrix(V)
    for e in range(E):
        s, t, d = map(int, input().split())
        w[s][t] = d

    result = dijkstra(r, w)
    for i in range(V):
        if result[i] == inf:
            print('INF')
        else:
            print(result[i])

main()