Lê Hoàng Phúc

#include <stdio.h>

#include <limits.h>

#define MAX 100

#define VOCUC INT_MAX

struct DoThi

{

    int n;

    int a[MAX][MAX];

};

int LuuVet[MAX];

int ChuaXet[MAX];

int DoDaiDuongDiToi[MAX];

void DSCsangMTK(DoThi &g)

{

    int m;

    scanf("%d %d", &g.n, &m);

    for (int i = 1; i <= g.n; i++)

    {

        for (int j = 1; j <= g.n; j++)

        {

            g.a[i][j] = VOCUC;

        }

    }

    for (int i = 0; i < m; i++)

    {

        int u, v, w;

        scanf("%d %d %d", &u, &v, &w);

        g.a[u][v] = w;

    }

}

int TimDuongDiNhoNhat(DoThi g)

{

    int li = -1;

    int p = VOCUC;

    for (int i = 1; i <=g.n; i++)

    {

        if (ChuaXet[i] == 0 && DoDaiDuongDiToi[i] != VOCUC && DoDaiDuongDiToi[i] < p)

        {

            p = DoDaiDuongDiToi[i];

            li = i;

        }

    }

    return li;

}

void CapNhatDuongDi(int u, DoThi g)

{

    ChuaXet[u] = 1;

    for (int v = 1; v <=g.n; v++)

    {

        if (ChuaXet[v] == 0 && g.a[u][v] < VOCUC)

        {

            if (DoDaiDuongDiToi[v] > DoDaiDuongDiToi[u] + g.a[u][v])

            {

                DoDaiDuongDiToi[v] = DoDaiDuongDiToi[u] + g.a[u][v];

                LuuVet[v] = u;

            }

        }

    }

}

void InDuongDi(int start, int end)

{

    if (LuuVet[end] == -1)

    {

        printf("%d ", start);

        return;

    }

    InDuongDi(start, LuuVet[end]);

    printf("%d ", end);

}

void Dijkstra(int S, int F, DoThi &g)

{

    if (S < 1 || S > g.n || F < 1 || F > g.n)

    {

        printf("-1\n");

        return;

    }

    for (int i = 1; i <= g.n; i++)

    {

        ChuaXet[i] = 0;

        DoDaiDuongDiToi[i] = VOCUC;

        LuuVet[i] = -1;

    }

    DoDaiDuongDiToi[S] = 0;

    while (ChuaXet[F] == 0)

    {

        int u = TimDuongDiNhoNhat(g);

        if (u == -1)

            break;

        CapNhatDuongDi(u, g);

    }

    if (ChuaXet[F] == 1 && DoDaiDuongDiToi[F] != VOCUC)

    {

        printf("%d\n", DoDaiDuongDiToi[F]);

        InDuongDi(S, F);

        printf("\n");

    }

    else

        printf("-1\n");

}

int main()

{

    DoThi g;

    DSCsangMTK(g);

    int start, end;

    scanf("%d", &start);

    scanf("%d", &end);

    Dijkstra(start, end, g);

    return 0;

}