ВСЕ ОТЛИЧНО
Информация о работе
Подробнее о работе
С++ Графы Алгоритм Дейкстры
- 1 страниц
- 2018 год
- 32 просмотра
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Дан неориентированный взвешенный граф.
Найти кратчайший путь между двумя данными вершинами.
Формат файла входных данных:
Первая строка входного файла содержит натуральные числа N и M (N ≤ 5000, M ≤ 100000) — количество вершин и ребер графа.
Вторая строка входного файла содержит натуральные числа S и F (1 ≤ S, F ≤ N, S ≠ F) — номера вершин, длину пути между которыми требуется найти
Следующие M строк по три натуральных числа bi, ei и wi — номера концов i-ого ребра и его вес соответственно (1 ≤ bi, ei ≤ N, 0 ≤ wi ≤ 100000).
Формат файла выходных данных:
Первая строка должна содержать одно натуральное число — вес минимального пути между вершинами S и F.
Во второй строке через пробел выведите вершины на кратчайшем пути из S в F в порядке обхода.
Если путь из S в F не существует, выведите -1.
#include
#include
#include
using namespace std;
struct dijkstra
{
int par, sum;
};
int a[5011][5011], c[5011], i, j, v, n, s, f, m, x, y, w;
dijkstra d[5011];
bool used[5011];
Дан неориентированный взвешенный граф.
Найти кратчайший путь между двумя данными вершинами.
Формат файла входных данных:
Первая строка входного файла содержит натуральные числа N и M (N ≤ 5000, M ≤ 100000) — количество вершин и ребер графа.
Вторая строка входного файла содержит натуральные числа S и F (1 ≤ S, F ≤ N, S ≠ F) — номера вершин, длину пути между которыми требуется найти
Следующие M строк по три натуральных числа bi, ei и wi — номера концов i-ого ребра и его вес соответственно (1 ≤ bi, ei ≤ N, 0 ≤ wi ≤ 100000).
Формат файла выходных данных:
Первая строка должна содержать одно натуральное число — вес минимального пути между вершинами S и F.
Во второй строке через пробел выведите вершины на кратчайшем пути из S в F в порядке обхода.
Если путь из S в F не существует, выведите -1.
Алгоритмы и структуры данных
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
