Темы --> Информатика --> Структуры данных --> Разреженные таблицы (sparse table)
---> 2 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 Отображать по:
#724
Берляндия атакует
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В этой задаче Вам вновь придется помочь Берляндии. Эта страна состоит из \(n\) городов, некоторые пары из которых соединены двусторонними дорогами, каждая дорога характеризуется своей длиной. Все города пронумерованы числами от 1 до \(n\), столица имеет номер 1. Время от време ни Президент объезжает страну, посещая города страны. Целью каждой поездки является один из городов, к которому он едет из столицы вдоль дорог одним из кратчайших путей.

В далекие времена (когда задачи на алгоритм Дейкстры вызывали сложность) специальное ведомство составила такой набор дорог \(T\), вдоль которого можно было проехать из столицы в любой город, причем единственным образом. Разумеется, путь по дорогам из набора \(T\) из столицы в каждый город являлся кратчайшим. Особо умные жители страны попросту называли этот набор дорог "деревом кратчайших путей". Известно, что Президент пользовался дорогами из \(T\) во время своих поездок. За прошедшие годы этот набор перестал быть секретным, и, поэтому, стал объектом повышенного внимания берляндских экстремистов. У специального ведомства новое задание. Для каждого города кроме столицы необходимо вычислить кратчайшее расстояние до него, при условии, что та дорога по которой Президент должен был закончить свой путь в этот город является атакованной и проезжать по ней нельзя.

Входные данные

В первой строке входного файла записана пара целых чисел \(n\) и \(m\) (\(2 \leq n \leq 4\,000\); \( n - 1 \leq m \leq 100\,000\)), где \(n\) — количество городов в стране, а \(m\)— количество дорог в этой стране. Далее в \(m\) строках содержатся описания дорог, по одной дороге в строке. Каждая дорога задается четверкой целых чисел \(a_j\), \(b_j\), \(l_j\), \(t_j\) , где \(a_j\), \(b_j\) это номера городов, соединяемых дорогой (\(1 \leq a_j, b_j \leq n\); \(a_j \neq b_j\)), \(l_j\) — ее длина (\(1 \leq l_j \leq 10^5\)), а \(t_j\) равно 1 если дорога принадлежит дереву кратчайших путей и 0 в противном случае.

Гарантируется, что набор \(T\) удовлетворяет описанным выше свойствам. Между парой городов может быть более одной дороги. Все дороги двусторонние.

Выходные данные

Выведите \(n - 1\) число в строку через пробелы. \(i\)-ое число должно быть равно либо длине кратчайшго пути из столицы в город \(i + 1\), при условии, что по той дороге из \(T\), которой Президент заканчивал свой путь в этот город, передвигаться нельзя, либо -1, если добраться до города \(i + 1\) вообще невозможно.

Примеры
Входные данные
5 9
3 1 3 1
1 4 2 1
2 1 6 0
2 3 4 0
5 2 3 0
3 2 2 1
5 3 1 1
3 5 2 0
4 5 4 0
Выходные данные
6 7 8 5
#113550
Антивещество
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
128 megabytes

Компания тестирует технологию получения антивещества, используемого в качестве топлива в межпланетном звездолёте. Антивещество получается в результате специальных экспериментов в реакторе.

Известно n типов экспериментов, приводящих к получению антивещества. В результате проведения эксперимента i-го типа в выходной контейнер реактора добавляется от li до ri граммов антивещества. Из соображений безопасности запрещается накапливать в контейнере более a граммов антивещества.

Затраты на проведение эксперимента i-го типа составляют ci, а стоимость одного грамма полученного антивещества составляет 109.

Если после проведения экспериментов в контейнере образовалось t граммов антивещества, а суммарные затраты на проведение экспериментов в реакторе составили s, то прибыль определяется по формуле (t·109 - s). Компании необходимо разработать стратегию проведения экспериментов, позволяющую максимизировать прибыль, которую можно гарантированно получить.

В зависимости от результатов предыдущих экспериментов стратегия определяет, эксперимент какого типа следует провести, или решает прекратить дальнейшее выполнение экспериментов. Стратегия позволяет гарантированно получить прибыль x, если при любых результатах проведения экспериментов: во-первых, в контейнере реактора оказывается не более a граммов антивещества, во-вторых, прибыль составит не менее x.

Например, пусть возможен только один тип эксперимента, порождающий от 4 до 6 граммов антивещества, затраты на его проведение равны 10, а вместимость контейнера составляет 17 граммов. Тогда после двукратного проведения эксперимента в контейнере может оказаться от 8 до 12 граммов антивещества. Если получилось 12 граммов, то больше проводить эксперимент нельзя, так как в случае получения 6 граммов антивещества контейнер может переполниться. В остальных случаях можно провести эксперимент в третий раз и получить от 12 до 17 граммов антивещества. В худшем случае придётся провести эксперимент трижды, затратив в сумме 30, прибыль составит (12·109 - 30) = 11 999 999 970.

Требуется написать программу, которая определяет максимальную прибыль x, которую гарантированно можно получить.

Входные данные

Первая строка входных данных содержит два целых числа: n — количество типов экспериментов и a — максимально допустимое количество антивещества в контейнере (1 ≤ n ≤ 100, 1 ≤ a ≤ 2 000 000).

Следующие n строк содержат по три целых числа li, ri и ci — минимальное и максимальное количество антивещества, получаемое в результате эксперимента типа i, и затраты на эксперимент этого типа, соответственно (1 ≤ li ≤ ri ≤ a, 1 ≤ ci ≤ 100).

Выходные данные

Выходные данные должны содержать одно целое число — максимальную прибыль x, которую гарантированно можно получить.

Примеры
Входные данные
1 17
4 6 10
Выходные данные
11999999970
Входные данные
2 11
2 2 100
3 5 5
Выходные данные
9999999890
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест