글 읽기 - 이 코드가 시간초과가 나는 이유가 뭘까요?

gwanwoo3849 10달 전 0

함수에서 u,v를 받아 만약 딕셔너리 d에 u,v의 최소 거리가 있으면 d[u,v]리턴,

없으면 딕셔너리에 경우별로 최소거리를 저장하면서 최소거리 구한 후 리턴하는데

dp방식에 메모이제이션을 했음에도 시간초과가 나는 이유를 잘 모르겠네요..

import sys
INF=10**6
sys.setrecursionlimit(INF)
d={}
def f(u,v):
    if (u,v) not in d:
        l=[]
        s=INF
        for i in range(1,n+1):
            if (u,i) in l:
                break
            elif (u,i) in d:
                l.append((u,i))
                k=f(i,v)
                if (i,v) in d:
                    d[(i,v)]=min(d[(i,v)],k)
                else:
                    d[(i,v)]=k
                s=min(s,k+d[(u,i)])
        d[(u,v)]=s
    return d[(u,v)]

n,e=map(int,input().split())
k=int(input())
for i in range(e):
  u,v,w=map(int,sys.stdin.readline().split())
  if (u,v) in d:
    d[(u,v)]=min(d[(u,v)],w)
  else:
    d[(u,v)]=w

for i in range(1,n+1):
  if k==i:
    print(0)
  else:
    s=f(k,i)
    if s==INF:
        print('INF')
    else:
        print(s)

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

문제

문제

출처

ICPC

이 코드가 시간초과가 나는 이유가 뭘까요?

gwanwoo3849 10달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말