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

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

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++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. Переполох у турникетов
 B. Поездка в кино
 C. Баобаб
 D. Очистка террасы
 E. Битва школ
 F. Этажи
 G. Космическое сновидение
 H. Неумолкающий Янпул
 I. ЦПСП
 J. Стреляй!
 K. Отряд Стёпы
 L. Swap optimization

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