글 읽기 - 테스트 케이스 추가 요청 드립니다.

duho1004 2년 전 0

이분탐색을 이용하지 않고 아래와 같이 각 정점별로 수치심을 작은 방향으로 갱신하며 진행하는 알고리즘이 통과됩니다.

5 5 0 4 10
0 1 2
1 2 2
2 3 2
0 3 4
3 4 6

위와 같은 테스트 케이스에서 6이 출력되어야 하나, -1로 잘못된 답을 리턴함에도 통과됩니다.

import sys
from math import log2
input = sys.stdin.readline
print(log2(10**9))
from heapq import heappop,heappush

n,m,a,b,c = map(int,input().rstrip().split())
graph = [[] for _ in range(n+1)]


for _ in range(m):
    f,t,cost = map(int,input().rstrip().split())
    graph[f].append((t,cost))
    graph[t].append((f,cost))

def dijkstra(node,target):
    heap = []
    minShame = [[float("inf"), float("inf")] for _ in range(n + 1)]

    heappush(heap,(0,0,node))   #현재 노드 / 수치심 / 사용 비용
    minShame[node] = [0,0]

    while heap:
        shame,cost,node = heappop(heap)
        if [shame,cost] > minShame[node]: continue
        if node == target:
            print(shame)
            exit()

        for nextnode,nextcost in graph[node]:
            resultShame = max(shame,nextcost)
            resultCost = cost + nextcost

            if resultCost > c or [resultShame,resultCost] >= minShame[nextnode]: continue

            minShame[nextnode] = [resultShame,resultCost]
            heappush(heap,(resultShame,resultCost,nextnode))
dijkstra(a,b)

print(-1)

hgh21233 1년 전 0

교차로는 1부터 시작이니 교차로 번호들에 다 +1씩 해주셔야 할 거 같네요

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

문제

문제

출처

ICPC

테스트 케이스 추가 요청 드립니다.

duho1004 2년 전 0

hgh21233 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말