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

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

HotLog


 

Баобаб

(Время: 5 сек. Память: 128 Мб Сложность: 53%)

«Элементарными называются такие истины, которые человек открывает последними.»
(с) Альбер Камю

Одним осенним вечером Егор прогуливался по ботанической оранжерее Мебибайтного Гибибайтного Универститета. Он повстречал на своём пути недавно открытое особенное дерево – баобаб. Он сразу заметил несколько свойств этого чудесного дерева и сформулировал важную для дальнейших исследований задачу.

Формально, вам дан неориентированный взвешенный граф без кратных ребер и петель, который называется баобабом. Баобаб представляет из себя один или более простых путей, имеющих общее начало в вершине 1 и общий конец в вершине n. Других общих вершин ни у каких двух путей нет. Каждый такой путь состоит из двух или более вершин. Каждое ребро описывается тремя числами u, v и c, которые обозначают ребро весом c между вершинами u и v.

Вам нужно ответить на q запросов — найти минимальный по весу путь от одной вершины до другой. Помогите Егору решить эту непростую задачу!

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

В первой строке входного файла INPUT.TXT записано три целых числа n, m и q (2 ≤ n ≤ 105; 1 ≤ m < 2×105; 1 ≤ q ≤ 2×105) — количество вершин, ребер и запросов.

В следующих m строках записано по три целых числа u, v, c (1 ≤ u, v ≤ n; 1 ≤ c ≤ 109), описывающие ребра графа.

В следующих q строках записано по два числа x, y (1 ≤ x, y ≤ n), задающие очередной запрос

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

В выходной файл OUTPUT.TXT Выведите q целых чисел — ответы на запросы в порядке появления запросов во входных данных.

Пример

INPUT.TXTOUTPUT.TXTПояснение
18 9 5
1 2 2
2 3 2
3 4 1
4 8 1
1 5 3
5 6 1
6 8 1
1 7 2
7 8 1
4 7
2 5
4 1
1 8
2 4
2 5 4 3 3

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая личная олимпиада
 Вторая личная олимпиада
 Третья личная олимпиада
 Четвертая личная олимпиада
 Пятая личная олимпиада
 Шестая личная олимпиада
 Седьмая личная олимпиада
 A. Календарь на Альфе Центавра
 B. Вложенные рамки
 C. Произведение
 D. Баобаб

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