Nguyễn Đức Gia Bảo

#include <stdio.h>

#include <stdlib.h>

#define MAX 100

#define VOCUC 1000

int LuuVet[MAX];

int ChuaXet[MAX];

int DoDaiDuongDiToi[MAX];

int SAU_NUT[MAX][MAX];

int L[MAX][MAX];

struct DOTHI {

int n;

int a[MAX][MAX];

};

void DStoMTK(struct 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] = 0;

}

}

int u, v, w;

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

{

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

g->a[u][v] = w;

}

}

int TimDuongDiNhoNhat(struct DOTHI g)

{

int li = -1;

float p = VOCUC;

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

{

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

{

p = DoDaiDuongDiToi[i];

li = i;

}

}

return li;

}

void CapNhatDuongDi(int u, struct DOTHI g)

{

ChuaXet[u] = 1;

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

{

if(ChuaXet[v] == 0 && g.a[u][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 Dijkstra(int S, int F, struct DOTHI g)

{

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)

{

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

int i = LuuVet[F];

while (i != -1)

{

printf("%d ", i);

i = LuuVet[i];

}

}else printf("-1");

}

void Floyd(struct DOTHI g)

{

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

{

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

{

if (g.a[i][j] > 0)

{

SAU_NUT[i][j] = j;

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

}

else

{

SAU_NUT[i][j] = -1;

L[i][j] = VOCUC;

}

}

}

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

{

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

{

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

{

if (L[i][j] > L[i][k] + L[k][j])

{

L[i][j] = L[i][k] + L[k][j];

SAU_NUT[i][j] = SAU_NUT[i][k];

}

}

}

}

int startVertex, targetVertex;

scanf("%d %d", &startVertex, &targetVertex);

if (SAU_NUT[startVertex][targetVertex] == -1)

{

printf("-1");

}

else

{

printf("%d\n", L[startVertex][targetVertex]);

printf("%d ", startVertex);

int u = startVertex;

while (SAU_NUT[u][targetVertex] != targetVertex)

{

u = SAU_NUT[u][targetVertex];

printf("%d ", u);

}

printf("%d ", targetVertex);

}

}

int main() {

struct DOTHI g;

DStoMTK(&g);

Floyd(g);

return 0;

}