Автор: | Р. Данилов | Ограничение времени: | 5 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Стивен устроился на работу программистом в новую транспортную компанию. В его обязанности входит оптимизация стоимости грузоперевозок из одной страны в другую.
В базе данных компании содержатся N городов, пронумерованных от 1 до N, и M односторонних дорог между некоторыми из них. Дорога номер i характеризуется тремя числами uivili — начальным городом, конечным городом и длиной дороги. Гарантируется, что ui≠vi, и не существует двух разных дорог i,j, для которых ui=uj,vi=vj.
Страна представляет из себя такое множество из одного или более городов, что:
Так как страны не дружат между собой, дороги из одной страны в другую находятся в плачевном состоянии. Это представляет главную проблему, поэтому стоимость перевозок внутри страны можно считать равной нулю. Стоимостью перевозки груза по дороге, соединяющей города из разных стран, будем считать длину этой дороги.
Запрос на перевозку определяется парой чисел sjfj — номерами города отправления и города назначения j-го груза. Напишите программу, которая для каждого из Q запросов определяет наименьшую возможную стоимость перевозки груза.
В тесте из примера имеется две страны. Одна состоит из городов 1,2,3, другая — из городов 4,5.
Входной файл содержит целые числа N M — количество городов и дорог соответственно.
Далее следует M троек целых чисел uivili — начальный город, конечный город и длина i-й дороги.
Далее следует целое число Q, за котором идут Q запросов по два целых числа sjfj — город отправления и город назначения j-го груза.
Выходной файл должен содержать Q целых чисел, каждое из которых равно наименьшей стоимости перевозки для соответствующего запроса, или −1, если эта перевозка невозможна.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|