글 읽기 - 다익스트라.. 잡손질이 조금 필요한듯한.. (도와주실분...주석 있어요..!)

sekeipost 1년 전 0

사알짝 응용이 들어간 다익스트라로 보이네요. 코드에 비효율적인 부분이 크게 있어보이진 않는데(있다면 같은 출발지와 같은 도착지에서 너무 비효율 적인 티켓들은 거를 방법이 없을까 생각해봤는데, 오히려 복잡해질거같아 하지 않았습니다), 혹시 조언 해주실 수 있는 부분이 있다면 해주시면 감사하겠습니다. ㅠㅠ

import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    neighbors = [set() for _ in range(N + 1)]
    distance_cost_arr = [[[] for _ in range(N + 1)] for __ in range(N + 1)]
    visited = [10 ** 9 for _ in range(N + 1)]
    for __ in range(K):
        u,v,c,d = map(int, input().split())
        neighbors[u].add(v) # 같은 경로가 나타날수 있으니 set로 관리
        distance_cost_arr[u][v].append([d, c]) #[distance, cost] 같은 경로더라도 여러 티켓이 있을수 있음에 유의
    heap = [[0, 0, 1]] #distance, cost, node_number
    result = -1
    while heap:
        current_distance, current_cost, current_node = heappop(heap)
        if current_node == N:
            result = current_distance
            break
        if visited[current_node] <= current_cost: # 현재 비용보다 적은 비용으로 노드를 방문한 적이 있으면 continue
            continue
        visited[current_node] = current_cost # 현재 비용 기록
        for neighbor in list(neighbors[current_node]):
            ne_inform = distance_cost_arr[current_node][neighbor]
            for ne_distance_cost in ne_inform:
                ne_distance, ne_cost = ne_distance_cost
                if ne_cost + current_cost <= M and visited[neighbor] > current_cost + ne_cost:
                    heappush(heap, [current_distance + ne_distance, current_cost + ne_cost, neighbor])
    if result == -1:
        result = 'Poor KCM'
    print(result)

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

문제

문제

출처

ICPC

다익스트라.. 잡손질이 조금 필요한듯한.. (도와주실분...주석 있어요..!)

sekeipost 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말