АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1228. Наилучший путь

Ограничение времени: 2 сек.
Ограничение памяти:131072 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

Имеется телекоммуникационная сеть, состоящая из N узлов. Некоторые пары узлов соединены каналами связи, для каждого канала известна его пропускная способность в обоих направлениях. Требуется найти путь для передачи трафика между двумя заданными узлами, имеющий максимальную пропускную способность. Пропускная способность пути равняется минимальной пропускной способности среди всех каналов (в соответствующем направлении), через которые он проходит.

Формат входных и выходных данных

В первой строке входных данных записаны через пробел четыре целых числа — N, M, a и b (2  N  1000, 0  M  10 000, 1 ≤ ab ≤ N, a ≠ b). Здесь N — количество узлов, M — количество каналов связи, a и b — номера начального и конечного узла.

В каждой из следующих M строк записано по 4 разделенных пробелами целых числа u, v, c1, c2 (1 ≤ u < v ≤ N, 1 ≤ c1c2 ≤ 1 000 000), где узлы u и v — концы очередного канала связи, c1 — пропускная способность в направлении от u к v, c2 — пропускная способность в направлении от v к u. Любые два узла соединены не более чем одним каналом.

В первой строке выходных данных выведите одно целое число — пропускную способность наилучшего пути. Если пути от a к b не существует, выведите 0. Если же путь существует, выведите в следующей строке через пробел номера узлов в порядке следования (первым узлом должен быть a, последним — b). Если подходящих путей несколько, то выведите путь с наименьшим количеством рёбер (каналов). Если таких путей также окажется больше одного, то выведите любой.

Пример

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

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

4 5 1 2

1 3 20 30

3 4 100 50

2 3 20 15

1 2 5 20

2 4 10 10

15

1 3 2

Примечание. На рисунке далее приведён граф сети для данного примера (число на ребре рядом с каждой вершиной показывает пропускную способность канала в направлении от неё).

 

Условия всех задач XVI межвузовской олимпиады в одном файле


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XVI Межвузовская олимпиада 2013 /
1227. H - Игра 1228. 1229. J - Синонимы 1230. K - Логическая схема
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, сентябрь 2020 / Импульс-2020, олимпиада закрытия, группа 1 /
176. 08 - Сообщение 1228. 296. 10 - Палиндром 1991. 11 - Подпалиндромы
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.