QBBUILD - Xây dựng đường
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
#define max 101
#define maxEC 50000
#define maxC max*maxEC
long c[max][max],Trace[max][max],n,a[5],min=maxC;
void Enter()
{
long u,v,x;
scanf("%ld",&n);
for(long i=1;i<=4;i++)
scanf("%ld",&a[i]);
for(u=1;u<=n;u++)
for(v=1;v<=n;v++)
{
if(u==v) c[u][v]=0;
else c[u][v]=maxC;
}
while(scanf("%ld %ld %ld",&u,&v,&x)>0&&x>0)
{
if(c[u][v]>x)
{
c[u][v]=x;
c[v][u]=x;
}
}
}
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 xuli()
{
for(long i=1;i<=n;i++)
for(int j = 1;j<=n;j++)
{
long mini=c[a[1]][i]+c[a[2]][i]+c[i][j]+c[a[3]][j]+c[a[4]][j];
if(mini<min)
min=mini;
//printf("%ld ",mini);
}
for(long i=1;i<=n;i++)
for(int j = 1;j<=n;j++)
{
long mini=c[a[1]][i]+c[a[4]][i]+c[i][j]+c[a[3]][j]+c[a[2]][j];
if(mini<min)
min=mini;
//printf("%ld ",mini);
}
for(long i=1;i<=n;i++)
for(int j = 1;j<=n;j++)
{
long mini=c[a[1]][i]+c[a[3]][i]+c[i][j]+c[a[4]][j]+c[a[2]][j];
if(mini<min)
min=mini;
//printf("%ld ",mini);
}
printf("%ld",min);
}
main()
{
Enter();
Floyd();
xuli();
//getch();
}