很裸的最小环，虽然本人是用floyed做的，但是感觉速度还行。。
有个地方要注意 答案跟顺序是无关的 如果答案是 1 2 3 你的结果是2 3 1也OK
不多说 直接上代码
#include<stdio.h>
long m,n,i,j,a,b,c,k,now,ans,num,p,first;
long map[101][101],f[101][101],fa[101][101];
long path[1001];
int main()
{
first=1;
while (2>1)
{
scanf("%ld",&n);
if (n==-1)
return 0;
if (first==1)
{
first=0;
}
else
printf("\n");
scanf("%ld",&m);
num=0;
for (i=1;i<=100;i++)
for (j=1;j<=100;j++)
{
map[i][j]=10000000;
f[i][j]=10000000;
fa[i][j]=0;
}
ans=10000000;
for (i=1;i<=m;i++)
{
scanf("%ld %ld %ld",&a,&b,&c);
if (map[a][b]>c)
{
map[a][b]=c;
map[b][a]=c;
f[a][b]=f[b][a]=c;
fa[a][b]=a;
fa[b][a]=b;
}
}
for (k=1;k<=n;k++)//floyed 最小环
{
for (i=1;i<=k-1;i++)//更新环长
for (j=i+1;j<=k-1;j++)
if (i!=k && i!=j && j!=k)
{
now=f[i][j]+map[i][k]+map[k][j];
if (now<ans)
{
ans=now;
num=1;
path[1]=k;
p=j;
while (p!=i)
{
num++;path[num]=p;
p=fa[i][p];
}
num++;path[num]=i;
}
}
for (i=1;i<=n;i++)//更新最短路
for (j=1;j<=n;j++)
if (i!=k && i!=j && j!=k)
{
if (f[i][j]>f[i][k]+f[k][j])
{
f[i][j]=f[i][k]+f[k][j];
fa[i][j]=fa[k][j];
}
}
}
if (num!=0)
{
for (i=1;i<=num;i++)
{
printf("%ld",path[i]);
if (i!=num)
printf(" ");
}
}
else
printf("No solution.");
}
}
posted on 2011-06-27 16:54
梦转千寻 阅读(74)
评论(0) 编辑 收藏 引用