https://www.acmicpc.net/problem/1240
initial
A very textbook bfs question at first glance but when I saw 1000x1000 matrix and the input that we can get value m was up to 1000, we cant manually do bfs 1000 times or it will cause runtime issues. I needa think of another way maybe floyd warshall? But while the time might be fixed, the 1000x1000 space would cause space issues. So how??
initial runtime code:
from collections import deque
import sys
input = sys.stdin.readline
def bfs(start, final, visited, graph):
queue = deque()
for j in range(1, n + 1):
if graph[start][j] != int(10e9):
visited[j] = True
queue.append([j, graph[start][j]])
while queue:
end, cost = queue.popleft()
if end == final:
return cost
for j in range(1, n + 1):
if graph[end][j] != int(10e9) and not visited[j]:
queue.append([j, cost + graph[end][j]])
visited[j] = True
n, m = map(int, input().split())
graph = [[int(10e9)] * (n + 1) for _ in range(n + 1)]
for _ in range(n - 1):
a, b, c = map(int, input().split())
graph[a][b] = c
graph[b][a] = c
for _ in range(m):
start, final = map(int, input().split())
visited = [False] * (n + 1)
val = bfs(start, final, visited, graph)
print(val)