FLOYD - Floyd hoặc Dijkstra ( Cơ bản )
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
#define max 1000
#define maxEC 1000
#define maxC max*maxEC
long c[max][max],Trace[max][max],n,a,b,T,x;
//FILE *p;
void Enter()
{
//p=fopen("D:\\Hoc tap\\test\\FLOYD\\FLOYD.IN0","r");
long m,u,v;
scanf("%ld %ld %ld",&n,&m,&T);
for(long u=1;u<=n;u++)
for(long v=1;v<=n;v++)
{
if(u==v) c[u][v]=0;
else c[u][v]=maxC;
}
for(long i=1;i<=m;i++)
{
scanf("%ld %ld",&u,&v);
scanf("%ld",&c[u][v]);
c[v][u]=c[u][v];
}
}
void Floyd()
{
for(long u=1;u<=n;u++)
for(long v=1;v<=n;v++)
Trace[u][v]=v;
for(long k=1;k<=n;k++)
for(long u=1;u<=n;u++)
for(long v=1;v<=n;v++)
if(c[u][v]>c[u][k]+c[k][v])
{
c[u][v]=c[u][k]+c[k][v];
Trace[u][v]=Trace[u][k];
}
}
void Result()
{
for(long i=1;i<=T;i++)
{
scanf("%ld %ld %ld",&x,&a,&b);
if(c[a][b]==maxC)
printf("-1\n");
else
{
if(x==0) printf("%ld\n",c[a][b]);
else
{
long t=1;
long d=a;
do
{
d=Trace[d][b];
t++;
}while(d!=b);
printf("%ld ",t);
do
{
printf("%ld ",a);
a=Trace[a][b];
}while(a!=b);
printf("%ld\n",b);
}
}
}
}
main()
{
Enter();
Floyd();
Result();
//getch();
}