글 읽기 - 파이썬 1916번 질문

roy2554 2년 전 0

잘 동작하는것 같은데 왜 틀렸다고 나올까요

입력

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

결과 : 4

입력

3
3
1 2 10
1 3 2
3 2 1
1 2

결과: 3

다 정상적으로 나옵니다

from heapq import heappush, heappop

INF = float('inf')

def dijkstra(**kwargs):
    graph = kwargs["graph"]
    dp    = kwargs["dp"]
    visit = kwargs["visit"]
    start = kwargs["start"]

    heap = []

    dp[start] = 0
    heappush(heap, [0, start])

    while heap:
        weight, node = heappop(heap)
        visit[node] = True

        for idx, value in enumerate(graph[node]):
            if value + weight < dp[idx]:
                dp[idx] = value + weight

        if list(filter(lambda x: x != INF and not visit[dp.index(x)], dp)):
            min_dp = min(list(filter(lambda x: x != INF and not visit[dp.index(x)], dp)))
            heappush(heap, [min_dp, dp.index(min_dp)])

    return dp

if __name__ == "__main__":
    city_cnt = int(input())
    bus_cnt = int(input())
    graph = [[INF for i in range(city_cnt + 1)] for j in range(city_cnt + 1)]
    for _ in range(bus_cnt):
        depart_city, arrive_city, cost = map(int, input().strip().split())
        if graph[depart_city][arrive_city] > cost:
            graph[depart_city][arrive_city] = cost

    dp = [INF] * (city_cnt + 1)
    visit = [False] * (city_cnt + 1)

    start, finish = map(int, input().strip().split())

    value = dijkstra(graph=graph, dp=dp, visit=visit, start=start)

    print(value[finish])
    
            

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

문제

문제

출처

ICPC

파이썬 1916번 질문

roy2554 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말