글 읽기 - 1916 최소비용구하기 메모리 초과 에러.. 고수님들 도와주세요..ㅠ

piousangel 2년 전 0

이코드에서 어떤 부분에서 메모리 초과가 나는지 궁금합니다. ㅠㅠ

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
M = int(input())

graph = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
for i in range(M):

    start, end, cost = map(int, input().split())

    graph[start].append([end, cost])


start_num, end_num = map(int, input().split())


def bfs(graph, visited, start_num, end_num) :
    global min_num 
    q = deque()

    q.append([start_num, 0])
    visited[start_num] = True

    while q :
        
        now, cost = q.popleft()

        if now == end_num :
            min_num = min(cost, min_num)
            


        for node in graph[now] :
            # if visited[node[0]] == False:
            #     visited[node[0]] = True
            q.append([node[0], cost + node[1]])


min_num = 100000
bfs(graph, visited, start_num, end_num)
print(min_num)

chldn323 2년 전 0

n이 1000이면 배열이 너무 커집니다. 인접 리스트를 적용해 보세요.

그리고 bfs 파라미터로 graph랑 visited를 전달할 필요는 없어 보입니다. 파이썬은 어떤지 모르겠는데 같은 크기의 객체가 하나 더 생길 수도 있어요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1916 최소비용구하기 메모리 초과 에러.. 고수님들 도와주세요..ㅠ

piousangel 2년 전 0

chldn323 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말