Задача #3125

Сортировка

Сложнее ЕГЭ

(Л. Шастин) Группа авантюристов хочет добраться до максимально возможно отдаленной от экватора зоны Земли, для чего им предстоит пересечь множество других зон в качестве перевалочных пунктов. При посещении очередной зоны авантюристы затрачивают некоторую сумму денежных единиц на организацию перевала, эта сумма может варьироваться в зависимости от отправной и конечной зоны. Начинает свой путь группа в зоне №1, а изначальные затраты средств равны нулю. Известно, что чем больше номер зоны, тем дальше она расположена от экватора. Из каждой зоны можно попасть только в зоны с большим номером. Имеется $N$ записей, каждая из которых содержит информацию о какой-то зоне: номер текущей зоны, номер переходной зоны, до которой можно добраться отсюда и сумма средств для посещения переходной зоны. Каждая зона может быть представлена в нескольких вариантах с разными переходными пунктами и ценами за переход. Некоторые записи также могут содержать информацию о недостижимых зонах (в которые невозможно попасть, начав движение из зоны №1). Определите номер максимальной зоны, которой могут достигнуть авантюристы, если их бюджет составляет $K$ денежных единиц, а также максимальный возможный остаток средств при этих условиях.

Входные данные
В первой строке входного файла находится два натуральных числа: $N (N \leq 100000)$ – количество записей о зонах и $K (K \leq 1000000)$ - бюджет, которым располагает группа. В каждой из следующих $N$ строк находятся по три числа: номер текущей зоны, номер переходной зоны (в которую можно передвинуться из текущей) и сумма средств, необходимая для перехода. Каждое из чисел натуральное, не превосходящее $1000000$ .
Запишите в ответе два числа: номер максимальной зоны, которой могут достигнуть авантюристы, если их бюджет составляет $K$ денежных единиц, а также максимальный возможный остаток средств при этих условиях.

Типовой пример организации данных во входном файле
8 100
1 4 20
2 4 30
1 3 10
3 4 5
4 5 5
1 2 10
3 5 20
2 5 50

При таких исходных данных можно достигнуть максимум зоны №5 несколькими способами. Оптимальным вариантом движения будет переход из зоны №1 в зону №3 за 10 ед., затем из зоны №3 в зону №4 за 5 ед. и в конце из зоны №4 в зону №5 за 5 ед. Остаток бюджета при этом составит 100 - 20 = 80 ед. Ответ: 5 80.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Файлы к задаче

Скачать 26.txt

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть

Ответ

4835

419

f = open('26_21588.txt')

N, K = [int(x) for x in f.readline().split()]

a = []
for s in f:
    fr, to, s = [int(x) for x in s.split()]
    a.append([to,fr, s])

a.sort()

d = {1:0}

for to,fr,s in a:
    if fr in d and d[fr]+s<=K:
        if to not in d:
            d[to] = d[fr]+s
        else:
            d[to] = min(d[to],d[fr]+s)

m = max(d.keys())
print(m, K-d[m])

Номер