글 읽기 - 다익스트라 시간초과

ddrrff 1년 전 0

시간 초과가 뜨는데 뭐가 문제일까요?

그리고 풀면서 궁금했던 건데

갔던 길 또 갈 수 있다고 조건에 써있잖아요.

1 -> x -> y -> N
1 -> y -> x -> N
이렇게 가는 거 외에

1 -> y -> x -> y -> N

이렇게 가는 게 더 최소일 수도 있는데

왜 저 2개의 경우만 생각하는 건가요?

import sys
import heapq
global N, graph
N, E = map(int, sys.stdin.readline().split())
graph = []
for i in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    graph.append([a, b, c])
x, y = map(int, sys.stdin.readline().split())


def f(start, end):
    dist = [float('inf')] * (N+1)
    queue = []
    dist[start] = 0
    heapq.heappush(queue, [0, start])
    while queue:
        current_cost, current_num = heapq.heappop(queue)
        if dist[current_num] < current_cost:
            continue
        for u, v, w in graph:
            if u == current_num:
                if dist[v] > dist[u] + w:
                    dist[v] = dist[u] + w
                    heapq.heappush(queue, [dist[v], v])

            elif v == current_num:
                if dist[u] > dist[v] + w:
                    dist[u] = dist[v] + w
                    heapq.heappush(queue, [dist[u], u])
    return dist[end]


result = min((f(1, x) + f(x, y) + f(y, N)), (f(1, y) + f(y, x) + f(x, N)))
print(result if result < float('inf') else -1)

jms020820 1년 전 0

되돌아오는 거리가 최단거리에 플러스 알파로 추가되니까 같은곳으로 되돌아와서 다시 목적지 까지 가는 경로가 최단경로가 될 수가 없죠..

문제의 같은곳을 여러번 방문 할 수 있다는 말은

1번째 경로) 1 -> x

2번째 경로) x -> y

3번째 경로) y -> N

2번째 경로에서 1번째 경로에서 방문했던 정점을 다시 방문 할 수 있다는 말입니다

3번째 경로에서는 1,2 번째 경로에서 방문했던 곳 상관없이 최단경로로만 가면 된다는 뜻이죠

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

문제

문제

출처

ICPC

다익스트라 시간초과

ddrrff 1년 전 0

jms020820 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말