글 읽기 - 9730 틀린 이유 도저히 모르겠습니다.. (주석있습니다.)

sekeipost 1년 전 0

아래와 같이 작성했는데 도저히 이유를 모르겠네요... 피드백 부탁 드립니다. 최대한 주석 달려고 노력했습니다.

from heapq import heappop, heappush
T = int(input())
INF = int(1e9)
total_result = []

for _ in range(T):
    n, m, t = map(int, input().split())
    s, g, h = map(int, input().split())
    visited = [False for _ in range(n + 1)]
    distance = [[INF for _ in range(n + 1)] for __ in range(n + 1)]
    pass_the_evidence = [False for _ in range(n + 1)] #이 점에 도달하기 까지 점선다리를 건넜는가
    neighbors = [[] for _ in range(n + 1)]
    result = [INF for _ in range(n + 1)] #이 점까지 최소 거리
    arrival = []
    for __ in range(m):
        a, b, d = map(int, input().split())
        neighbors[a].append(b)
        neighbors[b].append(a)
        distance[a][b] = d
        distance[b][a] = d
    heap = []
    result[s] = 0
    heappush(heap, [0, s, 1]) #[현재 이동 거리, 현재 위치, 점선다리 건넘 여부;false = 1, true = 0]
    while heap:
        """dist 와 cur 이 같다면 점선다리를 건넌 요소가 먼저 나오게 설정"""
        dist, cur, passing = heappop(heap)
        if visited[cur]:
            continue
        visited[cur] = True
        result[cur] = dist
        pass_the_evidence[cur] = passing
        for ne in neighbors[cur]:
            if visited[ne]:
                continue
            if result[ne] >= dist + distance[cur][ne]:#등호 이유 : 점선 건넘 유무만 다르고 거리는 같을 수 있음
                result[ne] = dist + distance[cur][ne]
                if (cur == g and ne == h) or (cur == h and ne == g): #점선 다리 건널 시
                    heappush(heap, [dist + distance[cur][ne], ne, 0])
                else:
                    heappush(heap, [dist + distance[cur][ne], ne, passing]) # 점선 다리 건넜는가 안건넜는가 상태 넘김
    for ___ in range(t):
        x = int(input())
        if pass_the_evidence[x] == 0:
            arrival.append(x)
    total_result.append(sorted(arrival))
for re in total_result:
    print(*re)

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

문제

문제

출처

ICPC

9730 틀린 이유 도저히 모르겠습니다.. (주석있습니다.)

sekeipost 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말