글 읽기 - 시간초과 질문

esc177 1년 전 0

전혀 반례를 못찾겠는데.. 혹시 찾아주실수있을까요

왜 시간초과가 되는지 이해가 안됩니다.

from collections import deque
import heapq


def solv(vec,n,start):
    weight= [2147483648]*(n+1)
    q=[]
    heapq.heappush(q,[0,start])
    weight[start]=0

    while(q):
        s_w,s = heapq.heappop(q)# start

        if weight[s]< s_w: continue
        # dp[now ] < wei
        for e in vec[s]:# dest
            e_w = vec[s][e]
            next_wei= s_w+e_w
            if(next_wei<weight[e]):#
                weight[e]= next_wei
                heapq.heappush(q,[weight[e],e])


    for i in range(1,n+1):
        if(weight[i]==2147483648): print("INF")
        else: print(weight[i])



if __name__=="__main__":

    n,m = map(int,input().split())
    start= int(input())
    vec = {}
    for i in range(1,n+1):
        vec[i]={}

    for i in range(m):
        s,e,w = map(int,input().split())
        vec[s][e]=w
    solv(vec,n,start)

dps2 1년 전 1

안녕하세요

왜인지는 모르겠으나 input이 매우 느립니다.

import sys

input = sys.stdin.readline 으로 input 함수를 조금 더 빠른 input함수로 대체가능합니다.

그런데 이렇게 하면 틀렸습니다가 뜰텐데요.

문제에 아래와 같이 적혀있습니다. 이것만 고려하면 맞았습니다를 볼 수 있으실 겁니다.

서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

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

문제

문제

출처

ICPC

시간초과 질문

esc177 1년 전 0

dps2 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말