Олимпиадный тренинг

Задача . Vacation Planning (gold)


Задача

Темы: кратчайшие пути

Air Bovinia выполняет полёты, соединяющие N (1 <= N <= 20,000) ферм, в которых живут коровы. K (1 <= K <= 200, K <= N) из этих ферм назначены хабами.
Сейчас Air Bovinia предлагает M (1 <= M <= 20,000) однонаправленных полётов, где полёт i производится из фермы ui в ферму vi и стоит di (1 <= di <=10,000) долларов. Для каждого из этих полётов или ui или vi является терминалом. Существует не более одного полёта между любыми двумя фермами в любом заданном направлении, и не существует полёта, который начинается и заканчивается в одной и той же ферме.
Беси руководитель службы занимающейся билетами. Получено Q (1 <= Q <= 50,000) однонаправленных запросов на путешествие, где i-ый запрос – перелёт из фермы ai на ферму bi.
Напишите программу, которая определит можно ли выписывать билет и, если да, то какова будет его минимальная стоимость.
Чтобы сократить размер вывода Вы должны вывести только общее количество билетов, которые можно выписать и суммарную их минимальную стоимость. Заметим, что это число может не поместиться в 32-битное целое.
PROBLEM NAME: vacationgold
Формат входных данных
* Строка 1: Целые числа N, M, K, Q.
* Строки 2..M + 1: Строка i+1 содержит ui, vi, и di. (1 <= ui, vi <= N, ui != vi)
* Строки M + 2..M + K + 1: Каждая из этих строк содержит ID одного хаба (в интервале 1..N).
* Строки M + K + 2..M + K + Q + 1: Два числа на строке, указывающие запрос на билет из фермы ai на ферму bi (1 <= ai, bi <=N, ai != bi)
Формат выходных данных
* Строка 1: Количество билетов, которые могут быть выписаны
* Строка 2: Минимальная общая стоимость всех выписанных билетов
Примечание
Для первого полёта есть только один маршрут 1->2->3 с ценой 20. Нет полётов из фермы 3, поэтому бедные коровы останутся там.
Примеры
№Входные данныеВыходные данные
1 
3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1
 
1
20
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет