1507 - Đường đi ngắn nhất

#include<stdio.h>
#include<string.h>

#define MAX 50
#define VOCUC 1000

typedef struct GRAPH
{
	int n;
	int a[MAX][MAX];
}DoThi;

//Khai báo các biến toàn cục
int LuuVet[MAX];
int ChuaXet[MAX];
int DoDaiDuongDiToi[MAX];

//Hàm để sao chép đồ thị từ danh sách cạnh sang ma trận kề
void SaoChep(DoThi &g) {
	//Nhập số đỉnh, số cạnh của danh sách cạnh
	int n, m;
	scanf("%d %d", &n, &m);
	
	g.n = n; // Sao chép số đỉnh
	
	// Khởi tạo ma trận kề
	for (int i = 1; i <= g.n; i++) {
		for (int j = 1; j <= g.n; j++) {
			g.a[i][j] = 0;
		}
	}
	
	// Thực hiện việc chuyển đổi từ danh sách kề sang ma trận kề và tính bậc của mỗi đỉnh
	for (int i = 1; i <= m; i++) {
		int u, v, w;    
		scanf("%d %d %d", &u, &v, &w);
		g.a[u][v] = w;	//Thêm trọng số w cho cạnh (u,v)
	}
}

//Hàm tìm đỉnh chưa xét có giá trị đường đi nhỏ nhất
int TimDuongDiNhoNhat(DoThi g)
{	
	int li = -1; //Kết quả trả về nếu không có đỉnh nào thoả mãn
	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;  //Trả về đỉnh chưa xét có giá trị đường đi nhỏ nhất
}

//Hàm cập nhật lại giá trị đường đi trong quá trình thi hành thuật toán tại đỉnh u
void CapNhatDuongDi(int u, DoThi g)
{	
	ChuaXet[u] = 1; //Đánh dấu đã xét đỉnh u
	for(int v = 1; v <= g.n; v++)
	{   
		//Tìm một đỉnh v chưa xét và có cạnh nối từ u sang v
		if(ChuaXet[v] == 0 && g.a[u][v] > 0 && g.a[u][v] < VOCUC) 
			/* Nếu như độ dài đường đi tới đỉnh v từ đỉnh khác mà lớn hơn 
				độ dài đường đi tới đỉnh u + cạnh (u,v) thì cập nhật lại */
			if(DoDaiDuongDiToi[v] > DoDaiDuongDiToi[u] + g.a[u][v]) 
			{	DoDaiDuongDiToi[v] = DoDaiDuongDiToi[u] + g.a[u][v];
				LuuVet[v] = u;
			}
	}
}

//Hàm để in kết quả đường đi từ S đến F
void KetQua_DeQui(int S, int F) {
	if (F != S)
		KetQua_DeQui(S, LuuVet[F]);
	printf("%d ", F);
}

//Hàm tìm đường đi ngắn nhất Dijkstra
void Dijkstra(int S,int F,DoThi g)
{
	//Khởi tạo các giá trị cần thiết cho thuật toán
	for(int i = 1; i <= g.n; i++)
	{
		ChuaXet[i] = 0;
		DoDaiDuongDiToi[i] = VOCUC;
		LuuVet[i] = -1;
	}
	
	DoDaiDuongDiToi[S] = 0;
	
	//Thi hành thuật toán Dijkstra
	while(ChuaXet[F] == 0)	//Lặp khi đỉnh F vẫn chưa được xét đến
	{	
		//Tìm đỉnh có độ dài đường đi nhỏ nhất ở bước hiện tại
		int u = TimDuongDiNhoNhat(g);
		if(u == -1) //Nếu không tìm được, dừng thuật toán
			break;
		CapNhatDuongDi(u, g); //Ngược lại cập nhật đường đi
	}
	//Xuất kết quả
	if(ChuaXet[F] == 1) //Có đường đi
	{	
		printf("%d\n",DoDaiDuongDiToi[F]);
		KetQua_DeQui(S, F);
	}
	else
		printf("-1");
}
//==============================================================
int main()
{
	DoThi g;
	
	SaoChep(g);
	
	int S, F;
			
	scanf("%d", &S);
	scanf("%d", &F);			
	
	Dijkstra(S,F,g);
		
	return 0;
}