글 읽기 - 10217 파이썬 메모리초과 문제... 해결부탁드립니다 ㅜㅜ

pgh94a 3년 전 0

정말 도저히 모르겠습니다...

메모리초과 해결방법 부탁드립니다 ㅜㅜ

이해를 도울 수 있는 주석 달아보았습니다.

import sys
from collections import deque
input = sys.stdin.readline

#bfs, 메모리초과
def bfs(start):
    queue=deque()
    queue.append( [start,0,0] )
    mv=[inf,inf] # 최소값을 위해 minimum values값 설정 , inf = sys.maxsize
    while queue:
        x,y,z = queue.popleft()
        if x==n: # x는 도착지 n을 의미. 만약 큐에서 pop한 값이 n과 같아지면 mv와 비교하여 더 작은 값으로 수정
            if y<=mv[0] and z<mv[1]:
                mv=[y,z]

        for arrive, prices, time in s[x]:
            if prices+y>m:
                continue
            queue.append( (arrive,prices+y,time+z) )
    if mv[1] == inf: # mv[0] = 가격 mv[1] = 시간, mv[1]으로 가는 경우가 없다면 inf가 됨.
        return 'Poor KCM'
    return mv[1]

inf = sys.maxsize
t=int(input()) # 테스트케이스
for _ in range (t):
    n,m,k = map(int,input().split()) # 공항개수, 가지고 있는 돈, 노선개수
    s=[[] for i in range (n+1)]
    for _ in range (k):
        u,v,c,d = map(int,input().split()) # u출발공항 v도착공항 c가격 d소요시간
        s[u].append( [v,c,d] )
    print(bfs(1))

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

문제

문제

출처

ICPC

10217 파이썬 메모리초과 문제... 해결부탁드립니다 ㅜㅜ

pgh94a 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말