vijos1046题解

题目：

学校里面有Ｎ个景点。两个景点之间可能直接有道路相连，用Dist[I，J]表示它的长度；否则它们之间没有直接的道路相连。这里所说的道路是没有规定方向的，也就是说，如果从I到J有直接的道路，那么从J到I也有，并且长度与之相等。学校规定：每个游客的旅游线路只能是一个回路（好霸道的规定）。也就是说，游客可以任取一个景点出发，依次经过若干个景点，最终回到起点。一天，Xiaomengxian决定到湖南师大附中旅游。由于他实在已经很累了，于是他决定尽量少走一些路。于是他想请你——一个优秀的程序员——帮他求出最优的路线。

这题是标准的floyd最小环问题（话说，我对这个经典算法还是有些疑惑，有想法的请留言）

切记切记，我已经多次犯一个同样的错误了：输出忘记换行。

在FP中，输出都习惯性的打成writeln，而C++的printf中\n功能不是很熟，因此老是忘记。

#include<stdio.h>
using namespace std;
long long f[101][101],map[101][101],ans,oo=99999999;
long i,j,k,n,m,x,y,z;
int main()
{
  while (scanf("%ld%ld",&n,&m)!=EOF)
  {
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        {
          f[i][j]=oo;
          map[i][j]=oo;
        }
    for (i=1;i<=m;i++)
      {
       scanf("%ld%ld%ld",&x,&y,&z);
        map[x][y]=z;map[y][x]=z;
        f[x][y]=z;f[y][x]=z;
      }
    ans=oo;
    for (k=1;k<=n;k++)
      {
      for (i=1;i<=k-1;i++)
        for (j=i+1;j<=k-1;j++)
          if(f[i][j]+map[i][k]+map[k][j]<ans)
           ans=f[i][j]+map[i][k]+map[k][j];
      for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
          if((f[i][k]+f[k][j]<f[i][j])) f[i][j]=f[i][k]+f[k][j];
      }
    if (ans<oo) printf("%ld\n",ans);
    else printf("No solution.\n");                   //注释：就是这里的\n没打
  }

附上之前错误的找环方案代码：（可能路径会重复）

 #include<stdio.h>
using namespace std;
const long oo=999999999;
long f[101][101],i,j,k,ans,n,m,x,y,z;
int main()
{
  while (scanf("%ld %ld",&n,&m)!=EOF)
  {
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        f[i][j]=oo;
    for (i=1;i<=m;i++)
      {
        scanf("%ld %ld%ld",&x,&y,&z);
        f[x][y]=z;f[y][x]=z;
      }
    for (k=1;k<=n;k++)
      for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
          if((i!=j)&&(i!=k)&&(k!=j)&&(f[i][k]+f[k][j]<f[i][j]))f[i][j]=f[i][k]+f[k][j];
    ans=oo;
    for (i=1;i<=n;i++)
    {
      for (j=1;j<=n;j++)
        for (k=1;j<=n;j++)
          if((i!=j)&&(i!=k)&&(j!=k)&&(f[i][j]+f[j][k]+f[k][i]<ans))
           ans=f[i][j]+f[j][k]+f[k][i];
    }
    printf("%ld\n",ans);
  }
}

巴特西

vijos1046题解

最新文章

热门文章