prim's algorithm

Run Settings
LanguageC
Language Version
Run Command
#include <stdio.h> #include <stdlib.h> #define INF 260 int main () { int i, j; // Переменные общего назначения int n, m, temp1, temp2, temp3; // Для ввода данных int v, to, answer = 0; // Для алгоритма int **graph; int *used; int *min_e; /* Ввод данных */ scanf("%d %d", &n, &m); graph = (int**)malloc(n * sizeof(int*)); used = (int*)malloc(n * sizeof(int*)); min_e = (int*)malloc(n * sizeof(int*)); for (i = 0; i < n; i++) { graph[i] = (int*)malloc(n * sizeof(int*)); for (j = 0; j < n; j++) { graph[i][j] = INF; } min_e[i] = INF; } for (i = 0; i < m; i++) { scanf("%d %d %d", &temp1, &temp2, &temp3); if (temp1 == temp2) { graph[temp1][temp2] = INF; graph[temp2][temp1] = INF; } else { graph[temp1][temp2] = temp3; graph[temp2][temp1] = temp3; } } /* Алгоритм */ min_e[0] = 0; for (i = 0; i < n; ++i) { v = -1; for (j = 0; j < n; ++j) { if (!used[j] && (v == -1 || min_e[j] < min_e[v])) { v = j; } } answer += min_e[v]; used[v] = 1; for (to = 0; to < n; ++to) { if (graph[v][to] < min_e[to]) { min_e[to] = graph[v][to]; } } } printf("%d\n", answer); for (i = 0; i < n; i++) { free(graph[i]); } free(graph); free(used); free(min_e); return 0; }
Editor Settings
Theme
Key bindings
Full width
Lines