#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
#define MAXINT 0x7FFF
int a[20][20],w[20][20],n,m;
int dd[20];
int min(int a, int b)
{
if(a<b) return a; else return b;
}
void docdlts()
{
FILE *f;
int i,j;
f=fopen("g9.cpp","rt");
if(f==NULL) cout<<"ko mo duoc file!";
else
{
int d,c,k;
fscanf(f,"%d%d",&n,&m);
for(i=1; i<=n; i++)
for(j=1; j<=n; j++) w[j]=MAXINT;
for(i=1; i<=m; i++)
{
fscanf(f,"%d%d%d", &d,&c,&k);
w[d][c]=w[c][d]=k;
}
cout<<"\n da doc xong file du lieu!";
fclose(f);
getch();
}
}
void dijkstra(int a, int z)
{
int i,j,v,x;
int L[100],T[100], HT[100]; //L nhan cac dinh,
// T la tap cac dinh
// HT : mang luu duong di tu a-->z
//buoc 1: Khoi gan
for(x=1; x<=n; x++) L[x]=MAXINT;
L[a]=0;
for(x=1; x<=n; x++) {T[x]=1; HT[x]=x;} //{T la tap cac dinh cua do thi G}
int dung=0;
while(dung==0)
{
//buoc 2
v=1; while(T[v]==0 && v<=n) v++; // tim v dau tien thuoc T
// Tim v thuoc T sao cho L[v] la nho nhat
for(j=v+1; j<=n; j++) if(T[j]==1 && L[j]<L[v]) v=j;
if(L[v]==MAXINT) {cout<<"\n DO THI KO LIEN THONG"; getch(); exit(1);}
T[v]=0; // loai v ra khoi tap T
//buoc 3
if (T[z]==0)
{
dung=1;
cout<<"\n duong di ngan nhat tu "<<a<<" den "<<z<<" la:"<<L[z];
// dua vao HT de in duong di
}
else
{
int r=L[x];
// xet cac dinh x thuoc T va ke v
for(x=1; x<=n; x++) if (T[x]==1 && w[x][v]!=MAXINT)
L[x]=min(L[x], L[v]+w[v][x]);
if (r!=L[x]) HT[x]=v; // cap nhat lai duong di den x
}
}
}
int main()
{
//clrscr();
docdlts();
for(int i=1; i<=n; i++)
{
cout<<"\n";
for(int j=1; j<=n; j++)
if(w[j]==MAXINT) {
//textcolor(2);
printf("%6c","c");
//textcolor(15);
}
else printf("%6d",w[j]);
}
dijkstra(1,9);
getch();
return 0;
}
