#include <stdio.h>
#include <stdlib.h>

int *flag, *path, *minpath, **graph, **matrix;
int min = 0;

int **loadthis(int **arr, int dts); // функция загрузки графа
void travel(int num_s, int num_d, int lenght, int dts);	//функция перебора
int **makematrix(int *arr1, int **arr2, int dts);
void savetofile(int **arr, int dts);


int main(void){
	int dots = 5;	//количество точек в графе
	//выделение динамической памяти под наши нужды
	flag = (int *)malloc(dots*sizeof(int));
	path = (int *)malloc(dots*sizeof(int));
	minpath = (int *)malloc(dots*sizeof(int));
	graph = (int **)malloc(dots * sizeof(int *));
	matrix = (int **)malloc(dots * sizeof(int *));
	for (int i = 0; i < dots; i++){
		graph[i] = (int *)malloc(dots * sizeof(int));
		matrix[i] = (int *)malloc(dots * sizeof(int));
	}

	loadthis(graph,dots);

	travel(0, 0, 0, dots);

	makematrix(minpath, matrix, dots);

	savetofile(matrix,dots);

	//высвобождение динамической памяти
	free(graph);
	free(matrix);
	free(path);
	free(minpath);
	free(flag);
	return 0;
}

int **loadthis(int **arr,int dts){
	FILE *file = fopen("graph.txt", "r");
	if (file == NULL){
		printf("Cannot open this file!\n");
		exit(0);
	}
	for (int i = 0; i < dts; i++){
		for (int j = 0; j < dts; j++){
			fscanf(file, "%d", &arr[i][j]);
		}
	}
	fclose(file);
	return arr;
}

void travel(int num_s, int num_d, int lenght,int dts){
	if (num_s == dts){
		if (min == 0 || lenght < min){
			min = lenght;
			for (int i = 0; i < dts; i++){
				minpath[i] = path[i];
			}
			return;
		}
	}
	if (flag[num_d] == 1)
		return;
	path[num_s] = num_d;
	flag[num_d] = 1;
	for (int i = 0; i < dts; i++){
		if (graph[num_d][i] == 0)
			continue;
		travel(num_s + 1, i, lenght + graph[num_d][i],dts);
	}
	flag[num_d] = 0;
}

int **makematrix(int *arr1, int **arr2, int dts){
	int tmp = 0, ttmp = 0;

	for (int i = 0; i < dts; i++){
		for (int j = 0; j < dts; j++){
			arr2[i][j] = 0;
		}
	}

	for (int i = 0; i < dts-1; i++){
		tmp = arr1[i];
		ttmp = arr1[i + 1];
		arr2[tmp][ttmp] = 1;
	}
	//костыль
	if (graph[ttmp][0] != 0)
		arr2[ttmp][0] = 1;
	return arr2;
}

void savetofile(int **arr,int dts){
	FILE *file = fopen("result.txt", "w + ");
	fprintf(file, "digraph {\n");
	for (int i = 0; i < dts; i++){
		fprintf(file, "  %d;\n", i + 1);
	}
	for (int i = 0; i < dts; i++){
		for (int j = 0; j < dts; j++){
			if (arr[i][j]>0){
				fprintf(file, "  %d -> %d [ label = \"%d\" ];\n", i + 1, j + 1, graph[i][j]);
			}
		}
	}
	fprintf(file,"}");
	fclose(file);
}