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

double count_weight(int* path, double** adjacency_matrix, int* size, int v_start) {
    double weight = adjacency_matrix[v_start][path[0]];
    for (int i = 0; i < *size - 1; i++) {
        weight += adjacency_matrix[path[i]][path[i + 1]];
    }
    return weight;
}

void dfs(int start, int end, int* path, int** shortest_path, double** adjacency_matrix,
         bool* visited, int n, int* size, int v_start, double* minimum_weight, int* final_size) {
    if (start == end) {
        double current_weight = count_weight(path, adjacency_matrix, size, v_start);
        if (current_weight < *minimum_weight) {
            *shortest_path = malloc((*size) * sizeof(int));
            for (int i = 0; i < *size; i++) {
                (*shortest_path)[i] = path[i];
            }
            *minimum_weight = current_weight;
            *final_size = *size;
        }
        return;
    }
    visited[start] = true;
    for (int i = 0; i < n; i++) {
        if (adjacency_matrix[start][i] > 0 && visited[i] == false) {
            path = realloc(path, ((*size) + 1) * sizeof(int));
            path[(*size)++] = i;
            dfs(i, end, path, shortest_path, adjacency_matrix, visited, n, size, v_start, minimum_weight, final_size);
            path = realloc(path, ((*size) - 1) * sizeof(int));
            (*size)--;
        }
    }
    visited[start] = false;
}

int main() {
    int n;
    printf("Podaj liczbe wierzcholkow: ");
    scanf("%d", &n);

    bool* visited = malloc(n * sizeof(bool));
    double** adjacency_matrix;
    adjacency_matrix = malloc(n * sizeof(double*));
    for (int i = 0; i < n; i++) {
        adjacency_matrix[i] = malloc(n * sizeof(double));
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adjacency_matrix[i][j] = 0;
        }
    }

    int v_s, v_e;
    printf("\nPodaj wierzcholek poczatkowy oraz koncowy: ");
    scanf("%d %d", &v_s, &v_e);

    int k;
    printf("\nPodaj liczbe przejsc: ");
    scanf("%d", &k);

    int s, e;
    double w;
    printf("\nPodaj zgodnie ze wzorem: <poczatek> <koniec> <waga>:\n");
    for (int i = 0; i < k; i++) {
        scanf("%d %d %lf", &s, &e, &w);
        adjacency_matrix[s - 1][e - 1] = w;
    }

    int* path = NULL;
    int* shortest_path;
    double min_weight = DBL_MAX;
    int size = 0;
    int temp_size = 0;
    dfs(v_s - 1, v_e - 1, path, &shortest_path, adjacency_matrix, visited, n, &temp_size, v_s - 1, &min_weight, &size);


    printf("Najkrtosza droga:\n");
    printf("%d->", v_s);
    for (int i = 0; i < size - 1; i++) {
        printf("%d->", shortest_path[i] + 1);
    }
    printf("%d", shortest_path[size - 1] + 1);
}