bairka
1

Алгоритм Флойда

28.01.2011, 11:07. Показов 2423. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Помогите решить задачу:

нужно найти кратчайшее расстояние между любыми двумя городами. всего городов N. А дорог M.

Во входном файле в первой строке входного файла заданы числа N и M ― количество городов и количество дорог между ними (1 ≤ N ≤ 100, 0 ≤ M ≤ 100000). Каждая из следующих M строк содержит тройку целых чисел A B C, описывающую дорогу из города A в город B, стоимость проезда по которой равна C (1 ≤ A, B ≤ N, A ≠ B, −1000 ≤ C ≤ 1000). Города нумеруются по порядку, начиная с единицы.

В выходной файл необходимо вывести N строк по N чисел, j-е число в i-й строке — минимальная стоимость проезда из города i в город j. стоимость пути из любого города в него же себя равно 0. Если до какого-то города пути нет, то необходимо вывести символ Z. Гарантируется, что нет такого циклического пути, стоимость проезда по которому от начала до конца отрицательна.
пример:
input:
5 7
1 2 1
1 4 -10
4 3 7
4 2 5
2 4 3
2 3 6
5 2 1

output:

0 -5 -3 -10 Z
Z 0 6 3 Z
Z Z 0 Z Z
Z 5 7 0 Z
Z 1 7 4 0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.01.2011, 11:07
Ответы с готовыми решениями:

Не могу разобраться, алгоритм Флойда
Задача такая. На ориентированном графе найти все отрицательные циклы если таковые имеются и вывести...

Алгоритм флойда - уоршелла находит не все пути
Пытаюсь реализовать этот алгоритм под c# и unity. вот создание начальных матриц. ...

Алгоритм Флойда — Уоршелла. Как же найти путь?
Реализовал нахождение длин кратчайшего пути между вершинами, но как найти сам путь так и не смог...

Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей]
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин...

1
5 / 5 / 1
Регистрация: 10.10.2008
Сообщений: 138
31.01.2011, 23:32 2
тут глянь
0
31.01.2011, 23:32
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.01.2011, 23:32
Помогаю со студенческими работами здесь

Печать кратчайшего пути из матрицы последовательности вершин (Алгоритм флойда)
Здравствуйте, проблема следующая: не могу получить список вершин из результирующей матрицы. В...

Алгоритмы Флойда-Уоршелла и Форда-Беллмана
Здравствуйте! Я не могу найти различие между двумя алгоритмами для нахождения минимального...

Алгоритм флойда
Здравствйте у меня есть беда. Есть вот такой код по вычеслению кратчайших путей и запоминание...

Алгоритм Флойда
Добрый вечер, помогите исправить ошибки в коде. #include <iostream> #include <time.h> #include...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru