В input написано 3 4 4
0 1 5
0 2 10
1 3 12
2 3 5
#define _CRT_SECURE_NO_WARNINGS
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int k;
int n;
int m;
scanf("%d", &k);
scanf("%d", &n);
scanf("%d", &m);
int *d; // минимальное расстояние
int *v; // посещенные вершины
int temp, minindex, min;
int begin_index = 0;
system("chcp 1251");
system("cls");
d = (int*)malloc(n * sizeof(int));
v = (int*)malloc(n * sizeof(int));
// Инициализация матрицы связей
int** a = { 0 };
a = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) // цикл по строкам
{
// Выделение памяти под хранение строк
a[i] = (int*)malloc(n * sizeof(int));
for (int j = 0; j < n; j++) // цикл по столбцам
{
a[i][j]=0;
}
}
int** b;
int c = 3;
b = (int**)malloc(m * sizeof(int*));
for (int i = 0; i < m; i++) // цикл по строкам
{
// Выделение памяти под хранение строк
b[i] = (int*)malloc(c * sizeof(int));
for (int j = 0; j < c; j++) // цикл по столбцам
{
scanf("%d", &b[i][j]);
}
}
for (int i = 0; i < m; i++)
for (int i = 0; i < m; i++) {
int j = 0;
int z = 0;
int x = 0;
int c = 0;
z = b[i][j];
x= b[i][j+1];
c= b[i][j + 2];
a[z][x] = c;
a[x][z] = c;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
printf("%5d ", a[i][j]);
printf("\n");
}
//Инициализация вершин и расстояний
for (int i = 0; i<n; i++)
{
d[i] = 10000;
v[i] = 1;
}
d[begin_index] = 0;
// Шаг алгоритма
do {
minindex = 10000;
min = 10000;
for (int i = 0; i<n; i++)
{ // Если вершину ещё не обошли и вес меньше min
if ((v[i] == 1) && (d[i]<min))
{ // Переприсваиваем значения
min = d[i];
minindex = i;
}
}
// Добавляем найденный минимальный вес
// к текущему весу вершины
// и сравниваем с текущим минимальным весом вершины
if (minindex != 10000)
{
for (int i = 0; i<n; i++)
{
if (a[minindex][i] > 0)
{
temp = min + a[minindex][i];
if (temp < d[i])
{
d[i] = temp;
}
}
}
v[minindex] = 0;
}
} while (minindex < 10000);
// Вывод кратчайших расстояний до вершин
printf("\nКратчайшие расстояния до вершин: \n");
for (int i = 0; i<n; i++)
printf("%5d ", d[i]);
// Восстановление пути
int *ver; // массив посещенных вершин
ver = (int*)malloc(n * sizeof(int));
int end = 4; // индекс конечной вершины = 5 - 1
ver[0] = end + 1; // начальный элемент - конечная вершина
int s = 1; // индекс предыдущей вершины
int weight = d[end]; // вес конечной вершины
while (end != begin_index) // пока не дошли до начальной вершины
{
for (int i = 0; i<n; i++) // просматриваем все вершины
if (a[i][end] != 0) // если связь есть
{
int temp = weight - a[i][end]; // определяем вес пути из предыдущей вершины
if (temp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[s] = i + 1; // и записываем ее в массив
s++;
}
}
}
// Вывод пути (начальная вершина оказалась в конце массива из s элементов)
printf("\nВывод кратчайшего пути\n");
for (int i = s - 1; i >= 0; i--)
printf("%3d ", ver[i]);
getchar(); getchar();
return 0;
}