Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.
В первой строке содержатся три числа: \(N\), \(S\) и \(F\) \((1 \leq N \leq 100, 1 \leq S, F \leq N)\), где \(N\) – количество вершин графа, \(S\) – начальная вершина, а \(F\) – конечная. В следующих \(N\) строках вводится по \(N\) чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.
Требуется вывести искомое расстояние или -1, если пути между указанными вершинами не существует.
| Ввод | Вывод |
|---|---|
3 2 1 0 1 1 4 0 1 2 1 0 |
3 |
В стране \(N\) городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге, требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в \(N\)-ый, потратив как можно меньше денег. Покупать бензин впрок нельзя.
В первой строке вводится число \(N\) \((1 \leq N \leq 100)\), в следующей строке идет \(N\) чисел, \(i\)-ое из которых задает стоимость бензина в \(i\)-ом городе (всё это целые числа из диапазона от 0 до 100). Затем идет число \(M\) – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.
Требуется вывести одно число – суммарную стоимость маршрута или -1, если добраться невозможно.
| Ввод | Вывод |
|---|---|
5 3 6 1 7 6 8 1 2 5 4 5 1 3 4 5 2 2 4 2 3 3 1 |
3 |
5 3 7 2 9 4 4 1 2 1 3 2 3 4 5 |
-1 |
Напишите программу, которая будет находить расстояния в неориентированном взвешенном графе с неотрицательными длинами ребер, от указанной вершины до всех остальных. Программа должна работать быстро для больших разреженных графов.
В первой строке входных данных задано число NUM — количество различных запусков алгоритма Дейкстры (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.
Первая строка блока содержит два числа \(N\) и \(M\), разделенные пробелом — количество вершин и количество ребер графа. Далее следуют \(M\) строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них в пределах от 0 до \(N–1\) каждое и обозначают концы соответствующего ребра, третье — в пределах от 0 до 20000 и обозначает длину этого ребра. Далее, в последней строке блока, записанное единственное число от 0 до \(N–1\) — вершина, расстояния от которой надо искать.
Количество различных графов в одном тесте NUM не превышает 5. Количество вершин не превышает 60000, рёбер — 200000.
Выведите на стандартный выход (экран) NUM строк, в каждой из которых по \(N_i\) чисел, разделенных пробелами — расстояния от указанной начальной вершины взвешенного неориентированного графа до его 0-й, 1-й, 2-й и т. д. вершин (допускается лишний пробел после последнего числа). Если некоторая вершина недостижима от указанной начальной, вместо расстояния выводите число 2009000999 (гарантировано, что все реальные расстояния меньше).
| Ввод | Вывод |
|---|---|
1 5 7 1 2 5 1 3 2 2 3 4 2 4 3 3 4 6 0 3 20 0 4 10 1 |
18 0 5 2 8 |
Дан ориентированный взвешенный граф. Найдите кратчайший путь от одной заданной вершины до другой.
В первой строке содержатся три числа: \(N\), \(S\) и \(F\) \((1 \leq N \leq 100, 1 \leq S, F \leq N)\), где \(N\) – количество вершин графа, \(S\) – начальная вершина, а \(F\) – конечная. В следующих \(N\) строках вводится по \(N\) чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.
Требуется вывести последовательно все вершины одного (любого) из кратчайших путей, или одно число -1, если пути между указанными вершинами не существует. В ответе примера указано количество вершин, а не сам путь. Ваша программа должна выдавать именно путь.
| Ввод | Вывод |
|---|---|
3 2 1 0 1 1 4 0 1 2 1 0 |
3 |
Между некоторыми деревнями края Васюки ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день.
Марии Ивановне требуется добраться из деревни \(d\) в деревню \(v\) как можно быстрее (считается, что в момент времени 0 она находится в деревне \(d\)).
Сначала вводится число \(N\) – общее число деревень \((1 \leq N \leq 100)\), затем номера деревень \(d\) и \(v\), за ними следует количество автобусных рейсов \(R (0 \leq R \leq 10000)\). Далее идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена – целые от 0 до 10000). Если в момент \(t\) пассажир приезжает в какую-то деревню, то уехать из нее он может в любой момент времени, начиная с \(t\).
Выведите минимальное время, когда Мария Ивановна может оказаться в деревне \(v\). Если она не сможет с помощью указанных автобусных рейсов добраться из \(d\) в \(v\), выведите -1.
| Ввод | Вывод |
|---|---|
3 1 3 4 1 0 2 5 1 1 2 3 2 3 3 5 1 1 3 10 |
5 |
К очередной Летней компьютерной школе было решено подготовить кружки как для школьников, так и для всех преподавателей.
Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. На то, чтобы довезти кружки от завода-изготовителя до ЛКШ, остаётся всего 24 часа.
Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?
В первой строке находятся числа \(n (1 \leq n \leq 500)\) и \(m\) - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих \(m\) строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.
Узловые пункты нумеруются числами от 1 до \(n\). При этом завод по производству кружек имеет номер 1, а ЛКШ - номер \(n\). Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик - 3 тонны.
Выведите одно число - максимальное количество кружек, которое можно привезти за первый рейс, потратив не более 24 часов.
| Ввод | Вывод |
|---|---|
3 3 1 2 10 3000220 2 3 20 3000201 1 3 1 3000099 |
2 |
В стране \(N\) городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге, требуется один бак бензина. Помимо этого у вас есть канистра для бензина, куда входит столько же топлива, сколько входит в бензобак.
В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в \(N\)-й, потратив как можно меньшее денег.
В каждом городе можно заправить бак, заправить бак и канистру или же перелить бензин из канистры в бак. Это позволяет экономить деньги, покупая бензин в тех городах, где он стоит дешевле, но канистры хватает только на одну заправку бака!
В первой строке вводится число \(N (1 \leq N \leq 100)\), в следующей строке идет \(N\) чисел, \(i\)-е из которых задает стоимость бензина в \(i\)-м городе (всё это целые числа из диапазона от 0 до 100). Затем идет число \(M\) – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.
Требуется вывести одно число – суммарную стоимость маршрута или -1, если добраться невозможно.
| Ввод | Вывод |
|---|---|
4 1 10 2 15 4 1 2 1 3 4 2 4 3 |
2 |