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:
# coding: utf-8
from heapq import heappush, heappop

class Node:
    def __init__(self, name):
        self.name = name
        self.edges_to = []
        self.edges_cost = []
        self.done = False
        self.cost = -1

if __name__ == "__main__":
    # set a graph
    V, E, r = map(int, raw_input().split())
    nodes = []
    for i in xrange(V):         # V??????Node????????????
        nodes.append(Node(i)) 
        
    for i in xrange(E):
        s, t, d = map(int, raw_input().split())
        nodes[s].edges_to.append(t)
        nodes[s].edges_cost.append(d)
    
    # dijkstra by priority queue(heapq)
    hq = []
    nodes[r].cost = 0           #?§????r???????????????0
    nodes[r].done = True  
    heappush(hq, nodes[r])
    
    while hq:          # r????????????????????????????????????????????????????±??????????
        done_node = heappop(hq)
        done_node.done = True
        for to, cost in zip(done_node.edges_to, done_node.edges_cost):
            new_cost = done_node.cost + cost
            if nodes[to].cost < 0 or new_cost < nodes[to].cost:
                nodes[to].cost = new_cost
                if nodes[to] not in hq:
                    heappush(hq, nodes[to])
            
    for item in nodes:
        if item.cost == -1:
            print "INF"
        else:
            print item.cost

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from heapq import heappush, heappop

class Node:
    def __init__(self):#, name):
        #self.name = name
        self.edges_to = []
        self.edges_cost = []
        #self.done = False
        self.cost = -1

if __name__ == "__main__":
    # set a graph
    V, E, r = map(int, raw_input().split())
    nodes = []
    for i in xrange(V):         # V??????Node????????????
        nodes.append(Node())#(i)) 
        
    for i in xrange(E):
        s, t, d = map(int, raw_input().split())
        nodes[s].edges_to.append(t)
        nodes[s].edges_cost.append(d)
    
    # dijkstra by priority queue(heapq)
    hq = []
    nodes[r].cost = 0           #?§????r???????????????0
    #nodes[r].done = True  
    heappush(hq, nodes[r])
    
    while hq:          # r????????????????????????????????????????????????????±??????????
        done_node = heappop(hq)
        #done_node.done = True
        for to, cost in zip(done_node.edges_to, done_node.edges_cost):
            new_cost = done_node.cost + cost
            if nodes[to].cost < 0 or new_cost < nodes[to].cost:
                nodes[to].cost = new_cost
                if nodes[to] not in hq:
                    heappush(hq, nodes[to])
            
    for item in nodes:
        if item.cost == -1:
            print "INF"
        else:
            print item.cost

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# TLE
from heapq import heappush, heappop

class Node:
    def __init__(self):#, name):
        #self.name = name
        self.edges_to = []
        self.edges_cost = []
        #self.done = False
        self.cost = -1

def dijkstra(nodes, start):
    # dijkstra by priority queue(heapq)
    hq = []
    nodes[start].cost = 0           #?§????start???????????????0
    #nodes[start].done = True  
    heappush(hq, nodes[start])
    
    while hq:          # start????????????????????????????????????????????????????±??????????
        done_node = heappop(hq)
        #done_node.done = True
        for to, cost in zip(done_node.edges_to, done_node.edges_cost):
            new_cost = done_node.cost + cost
            to_cost = nodes[to].cost
            if to_cost < 0 or new_cost < to_cost:
                nodes[to].cost = new_cost
                if nodes[to] not in hq:
                    heappush(hq, nodes[to])
                        
if __name__ == "__main__":
    # set a graph
    V, E, r = map(int, raw_input().split())
    nodes = []
    for i in xrange(V):         # V??????Node????????????
        nodes.append(Node())#(i)) 
        
    for i in xrange(E):
        s, t, d = map(int, raw_input().split())
        nodes[s].edges_to.append(t)
        nodes[s].edges_cost.append(d)
    
    dijkstra(nodes, r)
    
    for item in nodes:
        if item.cost == -1:
            print "INF"
        else:
            print item.cost

Submission status: Time Limit Exceeded

Solution code:
#??????????????????

graph = input()

V = int(graph.split(" ")[0])	#????????°
E = int(graph.split(" ")[1])	#????????°
s = int(graph.split(" ")[2])	#??????????????°???

d = []
for i in range(V):
	if i == s:
		d.append(0)
	else:
		d.append("INF")
#print("d: " + str(d))

dic = {}
for i in range(V):
	dic[i] = []

for i in range(E):
	x = input()
	dic[int(x.split(" ")[0])].append([int(x.split(" ")[1]), int(x.split(" ")[2])])
#print("dic: " + str(dic))

Q = []
for i in range(V):
	Q.append(i)
#print("Q: " + str(Q))

while len(Q) > 0:
	minNum = 1000000	#???????°???????????????????
	for i in Q:
		if d[i] == "INF":
			pass
		else:
			if minNum == 1000000:
				minNum = i
			elif d[minNum] > d[i]:
				minNum = i
#	print("minNum: " + str(minNum))
	Q.remove(minNum)
#	print("Q: " + str(Q))

	if len(dic[minNum]):
		for i in range(len(dic[minNum])):
			if d[dic[minNum][i][0]] == "INF":
				d[dic[minNum][i][0]] = d[minNum] + dic[minNum][i][1]
			elif d[dic[minNum][i][0]] > d[minNum] + dic[minNum][i][1]:
				d[dic[minNum][i][0]] = d[minNum] + dic[minNum][i][1]
#		print("d: " + str(d))

	endFrag = 1
	for i in Q:
		if d[i] != "INF":
			endFrag = 0
	if endFrag:
		break

for i in range(len(d)):
	print(d[i])

Submission status: Time Limit Exceeded

Solution code:
#??????????????????

graph = input()

V = int(graph.split(" ")[0])	#????????°
E = int(graph.split(" ")[1])	#????????°
s = int(graph.split(" ")[2])	#??????????????°???

d = []
for i in range(V):
	if i == s:
		d.append(0)
	else:
		d.append("INF")
#print("d: " + str(d))

dic = {}
for i in range(V):
	dic[i] = []

for i in range(E):
	x = input()
	dic[int(x.split(" ")[0])].append([int(x.split(" ")[1]), int(x.split(" ")[2])])
#print("dic: " + str(dic))

Q = {}
for i in range(V):
	Q[i] = d[i]
#print("Q: " + str(Q))

while len(Q) > 0:
	minNum = 1000000	#???????°???????????????????
	for i in Q.keys():
		if Q[i] == "INF":
			pass
		else:
			if minNum == 1000000:
				minNum = i
			elif Q[minNum] > Q[i]:
				minNum = i
#	print("minNum: " + str(minNum))
	del Q[minNum]
#	print("Q: " + str(Q))

	for i in range(len(dic[minNum])):
		alt = d[minNum] + dic[minNum][i][1]
		if d[dic[minNum][i][0]] == "INF":
			d[dic[minNum][i][0]] = alt
			Q[dic[minNum][i][0]] = alt
		elif d[dic[minNum][i][0]] > alt:
			d[dic[minNum][i][0]] = alt
			Q[dic[minNum][i][0]] = alt
#	print("d: " + str(d))

	endFrag = 1
	for i in Q.keys():
		if Q[i] != "INF":
			endFrag = 0
	if endFrag:
		break

for i in range(len(d)):
	print(d[i])

Submission status: Time Limit Exceeded

Solution code:
#??????????????????

graph = input()

V = int(graph.split(" ")[0])	#????????°
E = int(graph.split(" ")[1])	#????????°
s = int(graph.split(" ")[2])	#??????????????°???

d = []
for i in range(V):
	if i == s:
		d.append(0)
	else:
		d.append("INF")
#print("d: " + str(d))

dic = {}
for i in range(V):
	dic[i] = []

for i in range(E):
	x = input()
	dic[int(x.split(" ")[0])].append([int(x.split(" ")[1]), int(x.split(" ")[2])])
#print("dic: " + str(dic))

Q = {}
for i in range(V):
	Q[i] = d[i]
#print("Q: " + str(Q))

while len(Q) > 0:
	minNum = 1000000	#???????°???????????????????
	for i in Q.keys():
		if Q[i] == "INF":
			pass
		else:
			if minNum == 1000000:
				minNum = i
			elif Q[minNum] > Q[i]:
				minNum = i
#	print("minNum: " + str(minNum))
	del Q[minNum]
#	print("Q: " + str(Q))

	for i in range(len(dic[minNum])):
		alt = d[minNum] + dic[minNum][i][1]
		if d[dic[minNum][i][0]] == "INF":
			d[dic[minNum][i][0]] = alt
			Q[dic[minNum][i][0]] = alt
		elif d[dic[minNum][i][0]] > alt:
			d[dic[minNum][i][0]] = alt
			Q[dic[minNum][i][0]] = alt
#	print("d: " + str(d))

	endFrag = 1
	for i in Q.keys():
		if Q[i] != "INF":
			endFrag = 0
			break
	if endFrag:
		break

for i in range(len(d)):
	print(d[i])

Submission status: Time Limit Exceeded

Solution code:
#??????????????????

graph = input()

V = int(graph.split(" ")[0])	#????????°
E = int(graph.split(" ")[1])	#????????°
s = int(graph.split(" ")[2])	#??????????????°???

d = []
for i in range(V):
		d.append(1000000001)
d[s] = 0
#print("d: " + str(d))

dic = {}
for i in range(V):
	dic[i] = []

for i in range(E):
	x = input()
	dic[int(x.split(" ")[0])].append([int(x.split(" ")[1]), int(x.split(" ")[2])])
#print("dic: " + str(dic))

Q = {}
for i in range(V):
	Q[i] = d[i]
#print("Q: " + str(Q))

while len(Q) > 0:
	minNum = 1000000	#???????°???????????????????
	for i in Q.keys():
		if Q[i] > 1000000000:
			pass
		else:
			if minNum == 1000000:
				minNum = i
			elif Q[minNum] > Q[i]:
				minNum = i
#	print("minNum: " + str(minNum))
	del Q[minNum]
#	print("Q: " + str(Q))

	for i in range(len(dic[minNum])):
		alt = d[minNum] + dic[minNum][i][1]
		if d[dic[minNum][i][0]] > alt:
			d[dic[minNum][i][0]] = alt
			Q[dic[minNum][i][0]] = alt
#	print("d: " + str(d))

	endFrag = 1
	for i in Q.keys():
		if Q[i] < 1000000001:
			endFrag = 0
			break
	if endFrag:
		break

for i in range(len(d)):
	if d[i] > 1000000000:
		print("INF")
	else:
		print(d[i])

Submission status: Time Limit Exceeded

Solution code:
#??????????????????

graph = input()

V = int(graph.split(" ")[0])	#????????°
E = int(graph.split(" ")[1])	#????????°
s = int(graph.split(" ")[2])	#??????????????°???

d = []
for i in range(V):
		d.append(1000000001)
d[s] = 0
#print("d: " + str(d))

dic = {}
for i in range(V):
	dic[i] = []

for i in range(E):
	x = input()
	dic[int(x.split(" ")[0])].append([int(x.split(" ")[1]), int(x.split(" ")[2])])
#print("dic: " + str(dic))

Q = {}
for i in range(V):
	Q[i] = d[i]
#print("Q: " + str(Q))

while len(Q) > 0:
#	minNum = sorted(Q.items(), key=lambda x:x[1])[0][0]
	minNum = 1000000	#???????°???????????????????
	for i in Q.keys():
		if Q[i] < 1000000001:
			if minNum == 1000000:
				minNum = i
			elif Q[minNum] > Q[i]:
				minNum = i
#	print("minNum: " + str(minNum))
	del Q[minNum]
#	print("Q: " + str(Q))

	for i in range(len(dic[minNum])):
		alt = d[minNum] + dic[minNum][i][1]
		if d[dic[minNum][i][0]] > alt:
			d[dic[minNum][i][0]] = alt
			Q[dic[minNum][i][0]] = alt
#	print("d: " + str(d))

	endFrag = 1
	for i in Q.keys():
		if Q[i] < 1000000001:
			endFrag = 0
			break
	if endFrag:
		break

for i in range(len(d)):
	if d[i] > 1000000000:
		print("INF")
	else:
		print(d[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
inf = float('inf')

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

def sssp(r, w):
    V = len(w)
    result = inf_matrix(V)
    rest = list(range(V))
    rest.remove(r)
    var = [r]
    result[r][r] = 0

    while len(rest) > 0:
        costs = []
        for v in var:
            for res in rest:
                costs.append((result[r][v] + w[v][res], res))
        min_w, min_r = min(costs)
        if min_w == inf:
            break
        rest.remove(min_r)
        var.append(min_r)
        result[r][min_r] = min_w

    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 = sssp(r, w)
    for i in range(V):
        if result[r][i] == inf:
            print('INF')
        else:
            print(result[r][i])

main()

Submission status: Time Limit Exceeded

Solution code:
import heapq


class Edge:
    def __init__(self, dst, weight):
        self.dst, self.weight = dst, weight

    def __lt__(self, e):
        return self.weight > e.weight


class Graph:
    def __init__(self, V):
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, src, dst, weight):
        self.E[src].append(Edge(dst, weight))


class ShortestPath:
    """Dijkstra's algorithm : find the shortest path from a vertex
       Complexity: O(E + log(V))
       used in GRL1A(AOJ)
    """

    def __init__(self, G, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (all edge in E must be 0 or positive)
            start: start vertex
            INF: Infinity distance
        """
        self.G, self.INF = G, INF

    class Node:
        def __init__(self, v, cost):
            self.v, self.cost = v, cost

        def __lt__(self, n):
            return self.cost > n.cost

    def dijkstra(self, start, goal=None):
        que = list()
        self.dist = [self.INF] * self.G.V  # distance from start
        self.prev = [-1] * self.G.V  # prev vertex of shortest path
        self.dist[start] = 0
        heapq.heappush(que, self.Node(start, 0))

        while len(que) > 0:
            n = heapq.heappop(que)
            if self.dist[n.v] < n.cost:
                continue
            if goal is not None and n.v == goal:
                return
            for e in self.G.E[n.v]:
                if self.dist[n.v] + e.weight < self.dist[e.dst]:
                    self.dist[e.dst] = self.dist[n.v] + e.weight
                    heapq.heappush(que, self.Node(e.dst, self.dist[e.dst]))
                    self.prev[e.dst] = n.v

    def getPath(self, end):
        path = [end]
        while self.prev[end] != -1:
            end = self.prev[end]
        return path[::-1]

V, E, start = map(int, input().split())
G = Graph(V)
for _ in range(E):
    s, t, d = map(int, input().split())
    G.add_edge(s, t, d)
INF = 10**9
sp = ShortestPath(G, INF)
sp.dijkstra(start)
for i in range(G.V):
    print("INF" if sp.dist[i] == INF else sp.dist[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq


class Edge:
    def __init__(self, dst, weight):
        self.dst, self.weight = dst, weight

    def __lt__(self, e):
        return self.weight > e.weight


class Graph:
    def __init__(self, V):
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, src, dst, weight):
        self.E[src].append(Edge(dst, weight))


class ShortestPath:
    """Dijkstra's algorithm : find the shortest path from a vertex
       Complexity: O(E + log(V))
       used in GRL1A(AOJ)
    """

    def __init__(self, G, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (all edge in E must be 0 or positive)
            start: start vertex
            INF: Infinity distance
        """
        self.G, self.INF = G, INF

    class Node:
        def __init__(self, v, cost):
            self.v, self.cost = v, cost

        def __lt__(self, n):
            return self.cost > n.cost

    def dijkstra(self, start, goal=None):
        que = list()
        self.dist = [self.INF] * self.G.V  # distance from start
        self.dist[start] = 0
        heapq.heappush(que, self.Node(start, 0))

        while len(que) > 0:
            n = heapq.heappop(que)
            if self.dist[n.v] < n.cost:
                continue
            if goal is not None and n.v == goal:
                return
            for e in self.G.E[n.v]:
                if self.dist[n.v] + e.weight < self.dist[e.dst]:
                    self.dist[e.dst] = self.dist[n.v] + e.weight
                    heapq.heappush(que, self.Node(e.dst, self.dist[e.dst]))

V, E, start = map(int, input().split())
G = Graph(V)
for _ in range(E):
    s, t, d = map(int, input().split())
    G.add_edge(s, t, d)
INF = 10**9
sp = ShortestPath(G, INF)
sp.dijkstra(start)
for i in range(G.V):
    print("INF" if sp.dist[i] == INF else sp.dist[i])

Submission status: Time Limit Exceeded

Solution code:
maxd = 5000000001
nv, ne, r = [int(n) for n in input().split(' ')]
vertices = {k: {} for k in range(nv)}
for i in range(ne):
    s, t, w = [int(n) for n in input().split(' ')]
    vertices[s][t] = w

q = {v for v in vertices}
dist = {v: maxd for v in vertices}
dist[r] = 0

while len(q):
    min = maxd
    u = nv
    for v in q:
        if dist[v] <= min:
            min = dist[v]
            u = v

    q.remove(u)
    for v in vertices[u]:
        alt = dist[u] + vertices[u][v]
        if alt < dist[v]:
            dist[v] = alt

[print(d) if d < maxd else print("INF") for v, d in dist.items()]

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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 = [[source,0]]
    went = set()
    while queue != []:
        here,now_cost = queue.pop()
        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]
            queue.append([nw,next_cost])
        went = went | {here}
        queue.sort(key=lambda x:x[1],reverse=True)
    else:
        print("INF")

Submission status: Time Limit Exceeded

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}
    else:
        print("INF")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().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])
    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}
    else:
        print("INF")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().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 = 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}
    else:
        print("INF")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().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

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

Solution code:
from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().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

        can_go = link[here]

        #print(v,here,now_cost,not_went,queue)
        for nw in can_go:
            next_cost = now_cost + weight[here][nw]
            heapq.heappush(queue,(next_cost,nw))
        link[here] = can_go - {here}
    else:
        print("INF")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().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: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().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:1 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]:
        #print(v,here,now_cost,not_went,queue)
            for nw in link[here]:
                if went[nw]:
                    heapq.heappush(queue,(now_cost + weight[here][nw],nw))
            went[here] = 0
    else:
        print("INF")

Submission status: Time Limit Exceeded

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

    INF = 1000000000
    d = [INF] * nvertices
    d[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[u] + w < d[v]:
                d[v] = d[u] + w

    for val in d:
        if val >= INF:
            print("INF")
        else:
            print(val)


main()

Submission status: Time Limit Exceeded

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

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 j in range(v):
    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: Time Limit Exceeded

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 j in range(v):
    for i in range(v):
        for (t,d) in edge[i]:
            if d>=inf or dis[i]>=inf: continue
            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: Time Limit Exceeded

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

for j in range(v):
    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: 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)])

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


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


    setdist[r]=0
    '''initiating data'''


    for i in range(V-1):
        for j in range(len(edgeset)):
            newdist=edgeset[j][2]+setdist[edgeset[j][0]]
            olddist=setdist[edgeset[j][1]]
            if(newdist<olddist):
                setdist[edgeset[j][1]]=newdist
            
            

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

main()