#include <stdio.h>
#include <stdlib.h>
#define INFINITY 9999

int v[20], m[20][20], n;
char cale[64], len;

int dijkstra(int m[20][20], int start, int dest) {

    int d[20], t[20];
    int i, j, k = 0, l, s = 0, f = 0;
    int min, nod_min;

    start = start - 'a';
    dest = dest - 'a';

    nod_min = start;
    min = INFINITY;

    for (i = 0; i < n; i++) {
        v[i] = 0;
        d[i] = INFINITY;

        if (i == start)
            d[i] = 0;
    }

    for (i = 0; i < n; i++){
        min = INFINITY;

        for (j = 0; j < n; j++) {
            if ((d[j] < min) && v[j] == 0){
                nod_min = j;
                min = d[j];
            }
        }

        v[nod_min] = 1;

        for (j = 0; j < n; j++) {
            f = 0;
            if (m[nod_min][j] != 0) {
                if (d[j] > d[nod_min] + m[nod_min][j]) {
                    d[j] = d[nod_min] + m[nod_min][j];

                    for (l = 0; l < k; l++) {
                        if (t[l] == nod_min) {
                            f = 1;
                            break;
                        }
                    }

                    if (!f)
                        t[k++] = nod_min;
                }
            }
        }
    }

    for (i = 0; i < k; i++) {
        s += d[t[i]];

        cale[len] = t[i] + 'a';
        cale[len + 1] = ',';
        cale[len + 2] = ' ';
        cale[len + 3] = '\0';
        len += 3;
    }

    return s;
}
int main(){
    FILE *f = fopen("Text.txt", "r");
    int i, j;

    if (f == NULL)
        exit(EXIT_FAILURE);

    fscanf(f, "%d", &n);

    for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        fscanf(f, "%d", &m[i][j]);

    fclose(f);

    /*printf("Dati nodul de plecare: ");
    scanf("%d", &nod);
    printf("Dati nodul unde vreti sa ajungeti: ");
    scanf("%d", &destinatie);*/
    int c = dijkstra(m, 'a', 'c');
    printf("Calea cea mai scurta este: %s si are distanta %d  :", cale, c);
    return 0;
}