Кратчайшие пути в графе

Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти длину кратчайшего пути из вершины s в вершину t.

 

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

В первой строке заданы три числа: число вершин в графе N ≤50, номера вершин s и t. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от 0 до 1000000, число -1 означает отсутствие соответствующего ребра. Гарантируется, что на главной диагонали матрицы стоят нули.

 

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

Выведите одно число – минимальную длину пути. Если пути не существует, выведите -1.

Ввод	Вывод
3 1 2 0 -1 3 7 0 1 2 215 0	218

Между некоторыми деревнями края Васюки ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день.

 

Марии Ивановне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).

 

Сначала вводится число N – общее число деревень (1 <= N <= 100),  затем номера деревень d и v,  за ними следует количество автобусных рейсов R (0 <= R <= 10000). Далее идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена – целые от 0 до 10000). Если в момент t пассажир приезжает в какую-то деревню, то уехать из нее он может в любой момент времени, начиная с t.

 

Выведите минимальное время, когда Мария Ивановна может оказаться в деревне v. Если она не сможет с помощью указанных автобусных рейсов добраться из d в v, выведите -1.
 

В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге, требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее денег. Покупать бензин впрок нельзя.

 

В первой строке вводится число N (1≤N≤100), в следующей строке идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (всё это целые числа из диапазона от 0 до 100). Затем идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

 

Требуется вывести одно число – суммарную стоимость маршрута или -1, если добраться невозможно.

Дан ориентированный взвешенный граф. Найдите кратчайший путь от одной заданной вершины до другой.

 

В первой строке содержатся три числа: N, S и F (1≤N≤100, 1≤S, F≤N), где N – количество вершин графа, S – начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.

 

Требуется вывести последовательно все вершины одного (любого) из кратчайших путей, или одно число -1, если пути между указанными вершинами не существует. 

Примеры

№	Входные данные	Выходные данные
1	3 2 1 0 1 1 4 0 1 2 1 0	2 3 1

Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.

 

В первой строке содержатся три числа: N, S и F (1≤ N≤ 100, 1≤ S, F≤ N), где N – количество вершин графа, S – начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.
 

Требуется вывести искомое расстояние или -1, если пути между указанными вершинами не существует.

 

В неориентированном графе требуется найти минимальный путь между двумя вершинами. 

 

Формат входных данных
В первой строке записано число N - количество вершин в графе (1 <= N <= 100). В следующих строках задана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). В последней строке записаны номера двух вершин - начальной и конечной.

 

Формат выходных данных
Выведите сначала L - длину пути (количество ребер, которые нужно пройти). Затем выведите L+1 число - вершины в порядке следования вдоль этого пути. Если пути не существует, выведите одно число -1.

Дан неориентированный взвешенный граф с отрицательными весами, необходимо выдавать информацию о кратчайшем пути между 2 вершинами.

Входные данные
В первой строчке дано целое число n - количество вершин в графе. Дальше на вход подается матрица смежности, в которой -1 означает отсутствие ребра между вершинами. После матрицы идет число k - количество запросов, в следующих k строках содержится по 2 числа, a и b - вершины в запросе.

Выходные данные
Выведите k чисел - расстояние между парой чисел из запроса в порядке их ввода, если нельзя добраться из вершины a в вершину b, следует вывести Imp. Каждое число выводится в отдельной строке.

Дан неориентированный взвешенный граф, необходимо найти расстояние от вершины 1 до всех остальных, используя алгоритм Дейкстры.

 

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

В 1 строке даны 2 целых числа n и m (n>=1, m >= 0), число вершин и ребер в графе соответсвенно. В следующих m строках дается по 3 числа a и b - вершины которые соединяет ребро и c - вес этого ребра .

 

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

Необходимо вывести n-1 число через пробел - расстояния от вершины 1 до всех остальных, если нет возможного пути из 1 в i вершину, то необходимо вывести Impossible.

 

Ввод	Вывод
5 5 1 2 3 2 3 1 3 4 3 1 4 1 4 2 1	2 3 1 Impossible

 

P.S. Внимательно проверяйте ограничения

Дан ориентированный взвешенный граф с отрицательными ребрами (без отрицательных циклов).

Дана стартовая и конечная вершина, определить минимальное расстояние между ними.

 

Дано 4 числа n, m, s, f - количество вершин, количество ребер, стартовая и конечная вершина(начиная с 1) соответственно.

В следующих m строках содержится по 3 числа - вершина 1, вершина 2 и цена перехода между вершинами.

 

Требуется вывести одно число - ответ на поставленную задачу. Если ответа нет - следует вывести Inf.
 

В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.

 

Формат входных данных
В первой строке входных данных записано число N - количество вершин в графе (1 <= N <= 100). Далее с новой строки записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). В последней строке записаны номера двух вершин - начальной и конечной.

 

Формат выходных данных 
Выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.