글 읽기 - 9370) 다익스트라 파이썬 질문드립니다.

iamhelpingstar 7달 전 0

후보군에 대해 여러 경로로 갈 수 있기 때문에 다익스트라 함수에서 이하관계로 했고

도로를 지나쳤는지에 대한 판단부분은 아래 주석과 같습니다.

혹시 반례라도 알 수 있을까요 ㅠㅠㅠㅠ

# 최단경로가 여러개일 경우 틀릴 수 있다.

import sys
import heapq
input = sys.stdin.readline

T = int(input())

# 다익스트라를 한번만 실행한다.
def dijkstra(start, pass1, pass2):
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for next, new_dist in graph[now]:
            cost = new_dist + dist
            # 경로가 여러개일 수 있기 때문에 미만이 아닌 이하관계로 탐색을 진행한다.
            if cost <= distance[next]:
                distance[next] = cost
                heapq.heappush(q, (cost, next))
                # 현재가 도로를 지나간 상태면 다음것도 지나간 것일 것임
                if check_through[now]:
                    check_through[next] = True
                # 다리에 해당하는 곳을 지나쳤다면 next를 True로 바꾼다.
                elif (pass1, pass2) == (now, next) or (pass1, pass2) == (next, now):
                    check_through[next] = True

for _ in range(T):
    v, e, n_cand = map(int, input().split())
    start, pass1, pass2 = map(int, input().split())
    distance = [sys.maxsize] * (v+1)
    graph = [[] for _ in range(v+1)]
    # 지나갔는지를 체크하는 리스트
    check_through = [False] * (v+1)

    for _ in range(e):
        a, b, d = map(int, input().split())
        graph[a].append((b, d))
        graph[b].append((a, d))
    
    cands = []
    for _ in range(n_cand):
        cands.append(int(input()))

    # 다익스트라 호출 부분
    dijkstra(start, pass1, pass2)
    
    cands.sort()
    # 지나쳤다면 cands를 append해서 출력한다.
    ans = []
    for i in cands:
        if check_through[i]:
            ans.append(i)
    print(*ans)

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

문제

문제

출처

ICPC

9370) 다익스트라 파이썬 질문드립니다.

iamhelpingstar 7달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말