Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Pink Floyd

(Время: 1 сек. Память: 16 Мб Сложность: 74%)

Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.

Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелеты так, чтобы вес Роджера на каждом концерте был максимально возможным. Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.

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

Первая строка входного файла INPUT.TXT содержит три натуральных числа N, M и K – количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (N ≤ 100, M ≤ 104, 2 ≤ K ≤ 104). Города пронумерованы числами от 1 до n. Следующие M строк содержат описание рейсов, по одному на строке. Рейс номер i описывается тремя числами bi, ei и wi – номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (1 ≤ bi, ei ≤ N, −105 ≤ wi ≤ 105). Последняя строка содержит числа a1, a2, ..., aK – номера городов, в которых проводятся концерты. В начале концертного тура группа находится в городе a1. Гарантируется, что группа может дать все концерты.

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

Первая строка выходного файла OUTPUT.TXT должна содержать число S – количество рейсов, которые должна сделать группа. Вторая строка должна содержать S чисел – номера используемых рейсов. Если существует несколько решений, выведите любое.

Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то следует вывести «infinitely kind».

Примеры

INPUT.TXTOUTPUT.TXT
14 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 -10
1 3 1 2 4
6
5 6 5 7 2 3
24 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 10
1 3 1 2 4
infinitely kind

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Алгоритм Флойда
 B. Самый длинный путь
 C. Алгоритм Флойда - 2
 D. Флойд вместо Дейкстры
 E. Самый короткий путь
 F. Есть ли цикл?
 G. Транзитивное замыкание
 H. Два профессора
 I. Столовая
 J. Слабая K-связность
 K. Опасный маршрут
 L. Существование пути
 M. Pink Floyd

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru