Дан ориентированный взвешенный граф. Для него вам необходимо найти кратчайшее расстояние от вершины S до вершины F.
В первой строке входных данных содержатся три числа: N, S и F (1 <= N <= 100; 1 <= S, F <= N), где N – количество вершин графа. В следующих N строках записаны по N чисел – матрица смежности графа, где число в i-ой строке и j-ом столбце соответствует ребру из i в j: -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – наличие ребра данного веса. На главной диагонали матрицы всегда записаны нули.
Выведите искомое кратчайшее расстояние или -1, если пути между указанными вершинами не существует.
В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге, требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее количество денег.
В первой сроке вводится число N (1<=N<=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
Между некоторыми деревнями края Васюки ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день.
Марии Ивановне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).
Сначала вводится число N – общее число деревень (1 <= N <= 100), затем номера деревень d и v, за ними следует количество автобусных рейсов R (0 <= R <= 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
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
В первой строке вводится единственное число N (1 <= N <= 100) – количество вершин графа. В следующих N строках по N чисел задается матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы – всегда нули.
Выведите N строк по N чисел – матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j.
4 0 5 9 100 100 0 2 8 100 100 0 7 4 100 100 0
0 5 7 13 12 0 2 8 11 16 0 7 4 9 11 0
Дан ориентированный взвешенный граф. Вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.
В первой строке вводится единственное число N (1 <= N <= 100) – количество вершин графа. В следующих N строках по N чисел задается матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы – всегда нули.
Выведите искомое максимальное кратчайшее расстояние.
6 0 6 8 -1 -1 -1 5 0 5 -1 -1 -1 1 7 0 -1 -1 -1 -1 -1 -1 0 6 -1 -1 -1 -1 -1 0 3 -1 -1 -1 2 -1 0
9