글 읽기 - s의 범위에 대해 의문이 있습니다.

lsj6445z 3년 전 0

문제 상에서 s에 관해 주어진 범위는 0<=s<=1000으로 되어있습니다.

하지만 실제 코드에서 s의 초기값을 1001으로 설정하면 답이 틀리게 나옵니다.

대신 s의 초깃값을 1000만 이상으로 설정하면 정답이 나옵니다.

문제에 주어진 조건에 오류가 있는 것은 아닌지 여쭤봅니다.

제 코드에서 최대 s값을 설정한 부분은 15번 째 줄입니다.

import sys
import heapq

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
numTestcase = int(input())

for _ in range(numTestcase):
    n, d, c = map(int, input().split())    # n : 컴퓨터 수, d : 의존성 수, c : 감염원
    data = [[] for _ in range(n+1)]  # '인덱스'는 의존받는 대상(b), '값'은 [(x초 후 감염, 의존하는 대상(a))]
    for _ in range(d):
        a, b, s = map(int, input().split())    # 감염 방향: b -> a, s초 후 감염
        data[b].append((s, a))

    # 다익스트라 알고리즘
    dy = [10000000] * (n+1)    # 몇 초 후에 감염되는지 저장
    dy[c] = 0    # 감염원(c)은 0초 후에 감염
    q = [(0, c)]
    while q:
        timePassed, infectedCp = heapq.heappop(q)
        if dy[infectedCp] < timePassed:
            continue
        for s, a in data[infectedCp]:
            if dy[a] > s + timePassed:
                dy[a] = s + timePassed
                heapq.heappush(q, (s+timePassed, a))
    time = -1
    nCp = 0
    for i in range(1, n+1):
        if dy[i] != 10000000:
            time = max(time, dy[i])
            nCp += 1
    print(nCp, time)

lsj6445z 3년 전 0

10,000(최대 컴퓨터 개수) * 1,000 (감염에 걸리는 시간) = 10,000,000 초

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

문제

문제

출처

ICPC

s의 범위에 대해 의문이 있습니다.

lsj6445z 3년 전 0

lsj6445z 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말