글 읽기 - 다익으로 풀었는데 4%에서 막히는데 이유가 뭘까요?

aksndk123 2년 전 0

정점1번을 시작으로 다익스트라 돌려서 정점1번에서 가장먼 정점index1 구한다음에, index1을 기준으로 다익스트라를 돌려서 가장큰값을 출력하도록 코딩했습니다. 질문에 있는 예시들은 맞는데 4%에서 맞히네요. 반례나 틀린 알고리즘 알려주시면 감사하겠습니다.

import heapq
INF = int(1e10)


# 0 이면 가중치 없는거 1이면 가중치 있는거
def cal_dij(start, mod):
    global graph, V
    dij = [INF] * (V + 1)
    dij[0] = 0
    dij[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        now_value, now = heapq.heappop(q)
        if now_value > dij[now]:
            continue
        for target, target_value in graph[now]:
            dis = now_value + target_value
            if dis < dij[target]:
                dij[target] = dis
                heapq.heappush(q, (dis, target))
    if mod == 1:
        Max = max(dij)
        index1 = dij.index(Max)
        return index1
    elif mod == 2:
        return max(dij)



V = int(input())
graph = [[] for _ in range(V+1)]
for i in range(1, V+1):
    L = list(map(int ,input().split()))
    index = 1
    while L[index] != -1:
        a, b = L[index], L[index + 1]
        graph[i].append((a, b))
        index += 2
index1 = cal_dij(1, 1)
res = cal_dij(index1, 2)
print(res)

swoon 2년 전 1

다익스트라의 우선 순위를 가중치 큰 순으로 두더라도 최장 거리를 구할 순 없습니다.

aksndk123 2년 전 2

으 죄송하네요. 알고리즘이 틀린게 아니라 입력부분에서 1~ V+1 순으로 들어온다고 가정하고 입력을 받아서 틀렸습니다.

다익으로 풀어도 풀리긴 하는것 같습니다. 답변감사합니다!

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

문제

문제

출처

ICPC

다익으로 풀었는데 4%에서 막히는데 이유가 뭘까요?

aksndk123 2년 전 0

swoon 2년 전 1

aksndk123 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말