글 읽기 - 시간 초과 원인을 알려주시면 감사하겠습니다.

vrdhan212 1년 전 0

다익스트라 알고리즘 문제를 처음 풀어봤습니다.

문제에서는 노드 번호가 1번부터이지만,

저는 0번부터 만들어서 초기 거리를 무한대로 설정했고,

Shortest path 구할 적에 출발점부터 일반화 시켰습니다.

그러니까, 1번이 감염됐다면 1번의 거리가 0이기 때문에, 방문되지 않은 현재 노드로 설정되고 거리 갱신을 해주는걸 반복했습니다.

pypy3은 통과되는데, python3에서는 처음부터 시간 초과가 납니다.

이유를 알려주실 수 있을까요?

from collections import deque
import sys

input = sys.stdin.readline


def ShortestPath(graph):
    global visited, dist

    for _ in range(len(visited)):
        cur = 0
        # Find unvisited node which has shortest distance
        for n in range(1, len(visited)):
            if not visited[n] and dist[n] < dist[cur]:
                cur = n
        visited[cur] = True
        queue = deque(graph[cur])

        # Update shortest distance in terms of current node
        while queue:
            target, d = queue.popleft()
            diff = dist[cur] + d
            if diff < dist[target]:
                dist[target] = diff


for _ in range(int(input().strip())):
    n, d, c = map(int, input().strip().split())
    graph = list()
    visited = list()
    dist = list()
    total, time = 0, 0
    for i in range(n + 1):
        graph.append(list())
        visited.append(False)
        dist.append(float('inf'))
    dist[c] = 0

    for _ in range(d):
        tail, head, value = map(int, input().strip().split())
        graph[head].append([tail, value])

    # Dijkstra
    ShortestPath(graph)

    for num in range(1, len(visited)):
        if dist[num] != float('inf'):
            total += 1
            if time < dist[num]:
                time = dist[num]
    print(total, time)

choko100 1년 전 1

안녕하세요, heap 이 아닌 deque를 사용했기 때문에 다익스트라 탐색 시간이 오래 걸렸을 것 같습니다. heap 으로 변경하시면 python3 로도 통과될 것 같습니다.

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

문제

문제

출처

ICPC

시간 초과 원인을 알려주시면 감사하겠습니다.

vrdhan212 1년 전 0

choko100 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말