Тема
"Графы"

1. Задан набор неповторяющихся пар (A_i, A_j), где A_i, A_j принадлежат множеству А={A₁, A₂, ..., A_n}. Необходимо составить цепочку максимальной длины по правилу:
   (A_i, A_j) + (A_j, A_k) = (A_i, A_j, A_k).
   При образовании этой цепочки любая пара может быть использована не более одного раза.
2. Между N пунктами (N <= 50) заданы дороги длиной A(i,j), где i, j - номера пунктов. Дороги проложены на разной высоте и пересекаются только в общих пунктах. В начальный момент времени из заданных пунктов начинают двигаться с постоянной скоростью M роботов (M = 2 или 3), независимо меняя направление движения только в пунктах. Роботы управляются таким образом, чтобы минимизировать время до встречи всех роботов в одном месте. Скорость i-ого робота может быть равна 1 или 2 . Остановка роботов запрещена.
   Необходимо написать программу, которая:
   1. при заданных N, M и сети дорог единичной длины (все имеющиеся A(i,j) = 1) определяет минимальное время, через которое может произойти встреча всех M роботов, при этом начальное положение роботов и скорость их движения известны.
   2. выполнить те же действия, что и в п.1, но только для различных значений A(i,j).
   Примечание: В случае невозможности встречи всех M роботов в одном месте ни в какой момент времени в результате выполнения программы должно быть сформировано соответствующее сообщение.
   Требование к вводу-выводу:
   • Все входные данные - целые неотрицательные числа;
   • при задании сети дорог должно быть указано количество дорог - K и пункты их начала и конца в виде пар (i,j).
3. На плоскости расположено N точек. Имеется робот, который двигается следующим образом. Стартуя с некоторой начальной точки и имея некоторое начальное направление, робот движется до первой встреченной на его пути точки, изменяя в ней свое текущее направление на 90 градусов, т.е. поворачивая налево или направо. После этого он продолжает движение аналогично. Если робот достиг начальной точки, либо не может достичь новой точки (которую он еще не посещал), то он останавливается.
   Определить, может ли робот посетить все N точек, если:
   1. Определены начальные точка и направление робота.
   2. Определена начальная точка, а направление робота можно выбирать.
   3. Начальную точку и направление робота можно выбирать. Координаты точек - целые числа, угол измеряется в радианах относительно оси Ox.
4. Найти максимальное количество путей между двумя вершинами в графе, не пересекающиеся по
   1. ребрам;
   2. вершинам.
5. Лабиринт задается матрицей смежности C размера N*N, где C(i,j) = 1, если узел i связан узлом j посредством дороги. Часть узлов назначается входами, часть - выходами. Входы и выходы задаются последовательностями узлов X(1),...,X(р) и Y(1),...,Y(k) соответственно.
   Найти максимальное число людей, которых можно провести от входов до выходов таким образом, чтобы:
   1. их пути не пересекались по дорогам, но могут пересекаться по узлам;
   2. их пути не пересекались по узлам.
6. N шестеренок пронумерованы числами от 1 до N (N <= 10). Задано M (0 <= M <= 45) соединений пар шестерен в виде (i,j), 1 <= i < j <= N (шестерня с номером i находится в зацеплении с шестерней j).
   Необходимо определить, можно ли повернуть шестерню с номером 1?
   • Если да, то найти количество шестерен, пришедших в движение.
   • Если нет, то требуется убрать минимальное число шестерен так, чтобы в оставшейся системе при вращении шестерни 1 во вращение пришло бы максимальное число шестерен.
   Указать номера убранных шестерен (если такой набор не один, то любой из них) и количество шестерен, пришедших в движение.
7. Имеется N прямоугольных конвертов и N прямоугольных открыток различных размеров. Можно ли разложить все открытки по конвертам, чтобы в каждом конверте было по одной открытке?
   Замечание.
   Открытки нельзя складывать, сгибать и т. п., но можно помещать в конверт под углом. Например, открытка с размерами сторон 5:1 помещается в конверты с размерами 5:1, 6:3, 4.3:4.3, но не входит в конверты с размерами 4:1, 10:0.5, 4.2:4.2.
8. Составить программу для нахождения произвольного разбиения 20 студентов на 2 команды, численность которых отличается не более чем в 2 раза, если известно, что в любой команде должны быть студенты, обязательно знакомые друг с другом. Круг знакомств задается матрицей A размера 20x20 с элементами
   
   a[i,j] = 1, если i студент знаком со студентом j;
   a[i,j] = 0, если i студент не знаком со студентом j.
9. Имеется N человек и матрица А размера NxN. Элемент a[i,j] равен 1, если человек i знаком с человеком j (a[i,j] = a[j,i]). Можно ли разбить людей на 2 группы, чтобы в каждой группе были только незнакомые люди?
10. На олимпиаду прибыло N человек. Некоторые из них знакомы между собой. Можно ли опосредованно перезнакомить их всех между собой? (Незнакомые люди могут познакомиться только через общего знакомого).
11. Пусть группа состоит из N человек. В ней каждый имеет (N/2) друзей и не больше K врагов. У одного из них есть книга, которую все хотели бы прочитать и потом обсудить с некоторыми из остальных.
    Написать программу, которая:
    1. Находит способ передачи книги таким образом, чтобы она побывала у каждого в точности один раз, переходя только от друга к другу и наконец возвратилась к своему владельцу.
    2. Разбивает людей на S групп, где будет обсуждаться книга, таким образом, чтобы вместе с каждым человеком в ту же самую группу вошло не более Р его врагов.
    Примечание: предполагается, что S*Р >= K.
12. N различных станков один за другим объединены в конвейер. Имеется N рабочих. Задана матрица C размера NxN, где с[i,j] - производительность i-ого рабочего на j-ом станке.
13. Вводится N - количество домов и К - количество дорог. Дома пронумерованы от 1 до N. Каждая дорога определяется тройкой чисел - двумя номерами домов - концов дороги и длиной дороги. В каждом доме живет по одному человеку.
    Найти точку - место встречи всех людей, от которой суммарное расстояние до всех домов будет минимальным. Если точка лежит на дороге, то указать номера домов - концов этой дороги и расстояние от первого из этих домов. Если точка совпадает с домом, то указать номер этого дома.
    Примечание: длины дорог - положительные целые числа.
14. Янка положил на стол N выпуклых K-гранников и N различных типов наклеек по K штук каждая. Ночью кто-то наклеил наклейки на грани, по одной на грань. Помогите Янке расставить многогранники так, чтобы наклейка каждого типа была видна ровно K-1 раз.
15. Имеется N точек и M проводков. Проводком можно соединить некоторую пару различных точек, причем пара может быть соединена не более чем одним проводком. Все проводки должны быть использованы.
    Пусть D_i - количество проводков, которые будут соединены с точкой с номером i, i=1, ..., N. Необходимо соединить N точек с помощью M проводков таким образом, чтобы сумма S = D₁*D₁ + D₂*D₂ + ... + D_n*D_n была максимальной. Вывести величины D_i в неубывающем порядке и по требованию (рr=1), список соединений.
    Ввод:
    
    <Введите N:> N (N <= 100)
    <Введите M:> M (M <= 1000)
    <РR:> РRIZNAK
    Вывод:
    
    <Результирующая конфигурация:> Di в неубывающем порядке.
    <Сумма S> S
    <Список соединений>
    <Точку 1 соединить с> список точек
    .....
    <Точку N соединить с> список точек
16. Задано N городов c номерами от 1 до N и сеть из M дорог с односторонним движением между ними. Каждая дорога задается тройкой (i,j,k), где i - номер города, в котором дорога начинается, j - номер города, в котором дорога заканчивается, а k - её длина (число k - натуральное). Дороги друг с другом могут пересекаться только в концевых городах. Все пути между двумя указанными городами A и B можно упорядочить в список по неубыванию их длин (если есть несколько путей одинаковой длины, то выбираем один из них).
    Необходимо найти один из путей, который может быть вторым в списке. Вывести его длину L и города, через которые он проходит.
    Ввод:
    <Количество городов N:> N
    <Количество дорог M:> M
    <Начало, конец и длина дороги 1:> i₁, j₁, k₁
    ......
    <Начало, конец и длина дороги M:> i_M, j_M, k_M
    <Города A и B, между которыми надо найти путь:> A, B
    Вывод:
    <Пути нет> или <Путь проходит по городам> A, i₁, i₂, ..., B <Длина пути> L
17. Предположим, что есть страна с N городами. Дана система магистралей, соединяющая напрямую города между собой; длина любого прямого соединения равна 1. Такая система называется Четно-Нечетной, если любые два города, соединенные дорогой, соединены и дорогой четной длины, и дорогой нечетной длины.
    1. Выясните, является ли система магистралей Четно-Нечетной или нет;
    2. Если ответ на вопрос а) - отрицательный, найдите одно из подмножеств X из множества городов, в котором максимальное количество элементов, и оно удовлетворяет следующему условию: если какие-либо два города из X соединены путем, то его длина - четна.
    Имя входного файла вводится с клавиатуры. Его первая строка содержит значение N; следующие строки содержат I, J, означающие, что города I и J соединены напрямую. Значение N не превышает 300.
    Примеры:
    
    • Если входной файл содержит:
      5
      1 2
      2 3
      3 4
      4 5
      5 1
      
      допустимый ответ: YES
    • Если входной файл содержит:
      3
      1 2
      
      допустимый ответ: NO
      X has 2 elements (в множестве X два элемента)
      X: 2 3
18. Сеть дорог определяется следующим образом. Имеется N перекрестков и K дорог, связывающих перекрестки. Каждая дорога определяется тройкой чисел: двумя номерами перекрестков и временем, требующимся на проезд по этой дороге. Составить программу, находящую кратчайший путь машины от перекрестка i до перекрестка j, если на перекрестке машина должна ждать время, равное числу пересекающихся дорог. Движение по дороге возможно в обоих направлениях.
    Ввод:
    N K
    K троек чисел через пробелы
    i j
    
    Вывод: минимальное найденное время последовательность перекрестков от i до j, соответствующая найденному пути.
19. На прямоугольном участке размера 100*100 расположено N домиков (N < 31). Причем:
    • Левый нижний угол участка имеет координаты (0; 0), а правый верхний - (100; 100);
    • Местоположение каждого домика задается целочисленными координатами его нижнего левого угла;
    • Каждый домик имеет размер 5*5;
    • Стороны домиков параллельны сторонам участка;
    • Домики отстоят друг от друга не меньше чем на 1.
    Найти один из кратчайших путей от точки (0; 0) до точки(100; 100). Найденный путь представить в виде координат концов прямолинейных отрезков, составляющих этот путь, Вывести его длину с точностью до 0.1.
    Входные данные приготовлены в текстовом файле в следующем виде.
    число N
    x₁ y₁
    x₂ y₂
    . . .
    x_n y_n,
    где x_i, y_i - координаты левого нижнего угла i-го домика.
    Пример.
    Файл:
    1
    0 0
    Вывод:
    
    (0; 0) (0; 5) (100; 100)
    <Длина пути> 137.9
20. Скрудж Мак-Дак решил сделать прибор. Его механик Винт Р. спроектировал этот прибор таким образом, что он будет собираться из отдельных узлов, причем каждый узел уникален. Сами узлы в свою очередь могут требовать предварительной сборки. Для сборки каждого узла необходимо, чтобы все узлы, комплектующие его, были уже собраны. Узлы, не требующие сборки, обязательно тестируются на работоспособность. Собираемые узлы тестировать не требуется. На сборку одного узла или на его тестирование тратится один день. Готовый узел должен быть помещен на склад и может быть взят со склада только тогда, когда он необходим для сборки очередного узла или самого прибора. Хранение узла на складе в течении одного дня требует оплаты в размере одной условной денежной единицы. Необходимо организовать сборку таким образом, чтобы плата за аренду склада была минимальной.
    Схема сборки определяется во входном файле input1.txt по следующему формату:
    <1 строка> <общее количество узлов N>
    <2 строка> <номер узла, который нужно собрать>
    <3 строка> <номер узла>:<количество комплектующих>[:<список номеров комплектующих>]
    . . .
    <N+2 строка> <номер узла>:<количество комплектующих>[:<список номеров комплектующих>]
    Формат вывода:
    плата за аренду
    номер 1-го собираемого узла
    номер 2-го собираемого узла
    . . .
    номер прибора
    Примечание: узлы пронумерованы от 1 до N (N <= 50), прибор имеет номер 1.
    Внимание: разделителем чисел в пределах строки является символ ":" (двоеточие)
    

    Пример 1	Пример 2
    2	4
    1	1
    1:1:2	1:3:2:3:4
    2:0	2:0
    Ответ	3:0
    1	4:0
    2	Ответ
    1	6
    2
    3
    4
    1

21. Есть N карточек. На каждой из них черными чернилами написан её уникальный номер - число от 1 до N. Также на каждой карточке красными чернилами написано еще одно целое число, лежащее в промежутке от 1 до N (некоторыми одинаковыми "красными" числами могут помечаться несколько карточек).
    Например, при N=5, 5 карточек помечены следующим образом:

    "черное" число	1	2	3	4	5
    "красное" число	3	3	2	4	2

    Необходимо выбрать из данных N карточек максимальное число карточек таким образом, чтобы множества "красных" и "черных" чисел на них совпадали.
    Для приведенного выше примера это будут карточки с "черными" номерами 2,3,4 (множество красных номеров, как и требуется в задаче, то же - {2,3,4}).
    Ввод:
    <N = > N, N <= 50
    <"Черный" номер 1, "красный" -> "красное"_число_1
    ......
    <"Черный" номер N, "красный" -> "красное"_число_N
    Вывод:
    <В выбранном множестве элементов> количество_элементов S
    <"Черные" номера выбранных карточек> a1, ..., aS.
22. Пусть группа состоит из N человек. Назовем одного из этих людей знаменитостью, если он не знает никого из оставшихся, а его знают все. Задача состоит в том, чтобы в этой группе определить знаменитость (если она там есть). При этом разрешается задавать только вопросы вида "Извините, знаете ли Вы вон того человека?". (Предполагается, что все ответы правдивы, и что даже знаменитость ответит на поставленный ей вопрос).
    Найти минимально необходимое число вопросов, которое надо задать, и описать алгоритм опроса.
    Входные данные: матрица C[i,j], такая что C[i,j] = 1, если i знает j, и C[i,j]=0 иначе.
23. Винни-Пух и Пятачок нанялись защищать компьютерную сеть от хаккеров, которые выкачивали из компьютеров секретную информацию. Компьютерная сеть Винни-Пуха и Пятачка состояла из связанных между собой больших ЭВМ, к каждой из которых подключалось несколько терминалов. Подключение к одной из больших ЭВМ, позволяло получит информацию, содержащуюся в памяти этой ЭВМ, а также всю информацию доступную для ЭВМ, к которым данная ЭВМ могла направлять запросы. Хаккеры и раньше нападали на подобные компьютерные сети, и их тактика была известна. Поэтому Винни-Пух и Пятачок разработали специальную программу, которая помогла принять меры против готовившегося нападения.
    Тактика хаккеров.При нападении хаккеры всегда получают доступ к информации всех ЭВМ сети. Добиваются они этого, захватывая некоторые ЭВМ сети так, чтобы от них можно было запросить информацию у оставшихся ЭВМ. Вариантов захвата существует множество. Например, захватить все ЭВМ. Но хаккеры всегда выбирают такой вариант, при котором суммарное количество терминалов у захваченных ЭВМ минимально.
    Примечание. В сети у Винни-Пуха и Пятачка ни у каких двух ЭВМ количество терминалов не совпадает.
    Техническое задание. Вам необходимо написать программу, входными данными которой было бы описание сети, а выходными - список номеров ЭВМ, которые могут быть выбраны хаккерами для захвата сети согласно их тактике. Ввод осуществляется из файла с именем INPUT.TXT. Возможен ввод с клавиатуры.
    Формат ввода:
    Количество ЭВМ в сети: N
    ЭВМ #1 имеет терминалов: T[1]
    ЭВМ #2 имеет терминалов: T[2]
    . . . . . .
    ЭВМ #N имеет терминалов: T[N]
    Права на запрос:
    A[1] B[1]
    A[2] B[2]
    . . . .
    A[K] B[K]
    0 0
    где A[i] и B[i] - номера ЭВМ, последняя строка '0 0' обозначает конец списка прав на запрос. Каждая пара A[i] B[i] обозначает, что у ЭВМ с номером A[i] имеет право запрашивать у ЭВМ информацию с номером B[i] (A[i] не равно B[i]). При вводе числа N и T[i] - натуральные, T[i] <= 1000, N <= 50, K <= 2450. Входные данные соответствуют приведенным условиям.
    Формат вывода:
    Номера захватываемых ЭВМ : C[1] C[2] ... C[M]
    Количество захватываемых ЭВМ: M
    Пример:
    Количество ЭВМ в сети: 5
    ЭВМ #1 имеет терминалов: 100
    ЭВМ #2 имеет терминалов: 2
    ЭВМ #3 имеет терминалов: 1
    ЭВМ #4 имеет терминалов: 3
    ЭВМ #5 имеет терминалов: 10
    Права на запрос:
    1 3
    3 2
    4 3
    4 5
    5 4
    0 0
    Номера захватываемых ЭВМ : 1 4
    Количество захватываемых ЭВМ: 2
24. Скрудж Мак-Дак решил сделать прибор для управления самолетом. Как известно, положение штурвала зависит от состояния входных датчиков, но эта функция довольно сложна. Его механик Винт Разболтайло сделал устройство, вычисляющее эту функцию в несколько этапов с использованием промежуточной памяти и вспомогательных функций. Для вычисления каждой из функций требуется, чтобы в ячейках памяти уже находились вычисленные параметры (которые являются значениями вычисленных функций), необходимые для её вычисления. Вычисление функции без параметров может производиться в любое время. После вычисления функции ячейки могут быть использованы повторно (хотя бы для записи результата вычисленной функции). Структура вызова функций такова, что каждая функция вычисляется не более одного раза, и любой параметр используется не более одного раза. Любой параметр есть имя функции. Так как Скрудж не хочет тратить лишних денег на микросхемы, он поставил задачу минимизировать память прибора.
    По заданной структуре вызовов функций необходимо определить минимально возможный размер памяти прибора и указать последовательность вычисления функций. Входной файл INPUT.TXT или ввод с клавиатуры.
    Формат ввода:
    1-ая строка> <общее количество функций N>
    2-ая строка><имя функции,которую необходимо вычислить>
    3-ая строка> <имя функции> <количество параметров>
    [<список имен параметров>]
    . . . . . . . . . . . .
    (N+2)-ая строка> <имя функции> <количество параметров>
    [<список имен параметров>]
    Формат вывода:
    Размер памяти: <количество ячеек>
    Порядок:
    имя 1-й вычисляемой функции
    имя 2-й вычисляемой функции
    . . . .
    имя функции, которую необходимо вычислить
    Примечание: имя функции есть натуральное число от 1 до N.
    Пример:
    Ввод:
    5
    1
    1 2 2 3
    2 0
    3 2 4 5
    4 0
    5 0
    
    Вывод:
    Размер памяти: 2 ячейки
    Функция 4
    Функция 5
    Функция 3
    Функция 2
    Функция 1
25. Внутри пирамиды Хеопса есть N комнат, в которых установлены 2M модулей, составляющих M устройств. Каждое устройство состоит из двух модулей, которые располагаются в разных комнатах, и предназначено для перемещения между парой комнат, в которых установлены эти модули. Перемещение происходит за 0.5 условных единиц времени. В начальный момент времени модули всех устройств переходят в "подготовительный режим". Каждый из модулей имеет некоторый свой целочисленный период времени, в течении которого он находится в "подготовительном режиме". По истечении этого времени модуль мгновенно "срабатывает", после чего опять переходит в "подготовительный режим". Устройством можно воспользоваться только в тот момент, когда одновременно "срабатывают" оба его модуля. Индиана Джонс сумел проникнуть в гробницу фараона (комната. Обследовав её, он включил устройства и собрался уходить, но в этот момент проснулся хранитель гробницы. Теперь Джонсу необходимо как можно быстрее попасть в комнату N, в которой находиться выход из пирамиды. При этом из комнаты в комнату он может попадать только при помощи устройств, так как проснувшийся хранитель закрыл все двери в комнатах пирамиды.
    Необходимо написать программу, которая получает на входе описание расположения устройств и их характеристик (смотри описание формата ввода), а выдает значение оптимального времени и последовательность устройств, которыми надо воспользоваться, чтобы попасть из комнаты 1 в комнату N за это время.
    Входной файл: input2.txt
    Выходной файл: output2.txt
    Формат ввода:
    N
    M
    R₁₁ T₁₁ R₁₂ T₁₂
    . . . . .
    R_M1 T_M1 R_M2 T_M2
    где N (2 <= N <= 100) - количество комнат, M (M <= 100) - количество устройств, R_i1 и R_i2 - номера комнат, в которых располагаются модули устройства i, T_i1 и T_i2 (T_i1, T_i2 <= 1000) - периоды времени, через которые "срабатывают" эти модули. Все числа - натуральные. Входные данные будут соответствовать приведенным условиям.
    Пример:
    4
    5
    1 5 3 2
    1 1 2 1
    2 5 3 5
    4 4 3 2
    3 5 4 5
    Оптимальное время: 8.5
    Искомая последовательность: 2 3 4
26. План города представляет собой множество перекестков, соединённых дорогами. Перекрестки обозначаются точками на плоскости с коодинатами (x₁;y₁),(x₂;y₂),...(x_n;y_n), а дорогам соответствуют отрезки (i,j), где i и j обозначают номера перекрестков, которые эта дорога соединяет.
    Можно ли проехать от перекрестка с номером s до перекрестка с номером f, не делая левых поворотов, т.е. двигаясь только прямо или вправо? Если да, то указать последовательность перекрестков.
    Входные данные:
    В первой строке находятся числа n и m - количество перекрестков и количество дорог на плане соответственно. В каждой следующей строке сначала расположены координаты перекрестков, а затем номера перекрестков, которые связывает очередная дорога. В последней строке находятся номера s и f.
27. План города представляет собой множество перекестков, соединённых дорогами. Дорогам соответствуют пары (i,j), где i и j обозначают номера перекрестков, которые эта дорога соединяет. Для каждой дороги (i,j) известно время движения по ней T(i,j). Кроме того, время преодоления перекрестка i равно t*k(i), где t - заданная константа, а k(i) - количество дорог, подходящих к перекрестку i.
    Найти кратчайший по времени маршрут от перекрестка с номером s до перекрестка с номером f.
    Входные данные:
    В первой строке находятся числа n и m - количество перекрестков и количество дорог на плане соответственно. В каждой следующей строке сначала расположены номера пар перекрестков, которые связывает очередная дорога, и время её прохождения. В последней строке находятся номера s и f.
28. Дана система односторонних дорог, определяемая набором пар городов. Каждая такая пара (i,j) указывает, что из города i можно проехать в город j, но это не значит, что можно проехать в обратном направлении.
    Необходимо определить, можно ли проехать из заданного города А в заданный город В таким образом, чтобы посетить город С и не проезжать ни по какой дороге более одного раза.
    Входные данные задаются в файле с именем PATH.IN следующим образом. В первой строке находится натуральное N (N <= 50) - количество городов (города нумеруются от 1 до N). Во второй строке находится натуральное M(M <= 100) - количество дорог. Далее в каждой строке находится пара номеров городов, которые связывает дорога. В последней (M+3)-й строке находятся номера городов А, В и С.
    Ответом является последовательность городов, начинающаяся городом А и заканчивающаяся городом В, удовлетворяющая условиям задачи, который должен быть записан в файл PATH.OUT в виде последовательности номеров городов по одному номеру в строке. Первая строка файла должна содержать количество городов в последовательности. При отсутствии пути записать в первую строку файла число -1.
    Пример:
    3
    2
    1 2
    2 3
    1 3 2
    Ответ
    3
    1
    2
    3
29. Имеется N городов, которые пронумерованы от 1 до N (где N - натуральное, 1 < N <= 100). Некоторые из них соединены двухсторонними дорогами, которые пересекаются только в городах. Имеется два типа дорог - шоссейные и железные. Для каждой дороги известна базовая стоимость проезда по ней.
    Необходимо проехать из города А в город В, уплатив минимальную сумму за проезд. Стоимость проезда зависит от набора проезжаемых дорог и от способа проезда. Так, если вы подъехали к городу С по шоссейной (железной) дороге X->C и хотите ехать дальше по дороге C->Y того же типа, то вы должны уплатить только базовую стоимость проезда по дороге C->Y. Если тип дороги C->Y отличен от типа дороги Х->C, то вы должны уплатить базовую стоимость проезда по дороге C->Y плюс 10% от базовой стоимости проезда по этой дороге (страховой взнос). При выезде из города А страховой взнос платится всегда.
    Написать программу, которая находит самый дешевый маршрут проезда в виде последовательности городов и вычисляет стоимость проезда по этому маршруту.
    Спецификация входных данных.
    Входные данные находятся в текстовом файле с именем TOUR.IN и имеют следующий формат:
    
    • в первой строке находятся число N;
    • во второй строке - число M (количество дорог, натуральное M <= 1000);
    • в каждой из следующих M строк находятся 4 числа x, y, t, p, разделённые пробелом, где x и y - номера городов, которые соединяет дорога, t - тип дороги (0 - шоссейная, 1 - железная), p - базовая стоимость проезда по ней (p - вещественное число, 0 < p <= 1000).
    • в последней строке задается номера начального и конечного городов A и B.
    Спецификация выходных данных.
    Выходные данные должны быть записаны в текстовый файл с именем TOUR.OUT и иметь следующий формат:
    • в первой строке находится число S - стоимость проезда по самому дешевому маршруту, с точностью 2 знака после запятой;
    • в каждой из последующих строк, кроме последней, находится два числа - номер очередного города в маршруте (начиная с города А) и тип дороги, по которой он выезжает из этого города (0 или 1), разделённые пробелом.
    • в последней строке находится единственное число - номер города B.
    Пример входного файла TOUR.IN
    
    >3
    2
    1 2 0 10.00
    2 3 1 10.00
    1 3
    Пример выходного файла TOUR.OUT
    
    22.0
    1 0
    2 1
    3
30. Даны декартовы координаты N перекрестков города, которые пронумерованы от 1 до N. На каждом перекрестке имеется светофор. Некоторые из перекрестков соединены дорогами с двухсторонним (правосторонним) движением, которые пересекаются только на перекрестках. Для каждой дороги известно время, которое требуется для проезда по ней от одного перекрестка до другого.
    Необходимо проехать от перекрестка с номером А до перекрестка с номером В за минимальное время. Время проезда зависит от набора проезжаемых дорог и от времени ожидания на перекрестках. Так, если вы подъехали от перекрестка X к перекрестку C по дороге Х->C и хотите ехать дальше по дороге C->У, то время ожидания на перекрестке C эависит от того, поворачиваете ли вы налево или нет. Если вы поворачиваете налево, то время ожидания равно D*К, где D равно количеству дорог, пересекающихся на перекрестке C, а К - некоторая константа. Если вы не поворачиваете налево, то время ожидания равно нулю. Написать программу, которая определяет самый быстрый маршрут.
    Спецификация входных данных.
    Входные данные находятся в текстовом файле с именем PER.IN и имеют следующую структуру:
    • в первой строке находится число N (натуральное, <=1000);
    • во второй строке - количество дорог M (натуральное, <=1000);
    • в третьей строке - константа K (натуральное число, <=1000);
    • в каждой из N следующих стpок находится паpа чисел х и у, разделённых пробелом, где x, y - кооpдинаты перекрестка (целые числа, не пpевышающие по модулю 1000);
    • в каждой из M следующих строк находится 3 числа p, r, t, разделённые пробелом, где p и r - номера перекрестков, которые соединяет дорога, а t (натуральное, <=1000) - время проезда по ней;
    • в последней строке находятся номера начального А и конечного В перекрестков.
    Спецификация выходных данных.
    Выходные данные должны быть записаны в текстовый файл с именем PER.OUT и иметь следующий формат:
    • в первой строке находится натуральное число T - время проезда по самому быстрому маршруту;
    • в каждой из следующих строк находится одно число - номер очередного перекрестка в маршруте (начиная с перекрестка с номером А и кончая В).

    Главная

    Предыд.

    След.

    Др. раздел