LOJ10072 Sightseeing Trip

题意

求无向图最小环，要求输出路径。

其中点数 $N\le 100$

题解

本来求最小环挺简单的，恶心的就是这道题还要求输出路径。

求最小环的方法就是用 $spfa$ 跑最短路，得到最初的距离 $dis[u][v]$ 和最短路 $mn[u][v]$ 。那么对于每个节点 $x$ ，它与 $u$ 和 $v$ 相邻，那么他们最小环的长度即为：

$$mn[u][v]+dis[x][u]+dis[x][v]$$

每次更新答案即可。

这道题要求记录路径，事实上我们只需要记录 $u$ 和 $v$ 之间最短路的路径就行了。维护一个数组 $pre[i][j]$ ，表示要从 $j$ 跳到 $i$ 路径的上一步，每次跑最短路时更新即可。

需要注意的是 $inf$ 开 $1e9$ 会爆，开 $1e8$ 就行了。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int dis[105][105],pre[105][105],mn[105][105],rd[105],n,m,a,b,c,ans,cnt;

int main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            pre[i][j]=i;
            dis[i][j]=mn[i][j]=1e8;
        }
    }
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        if (c>=dis[a][b]) continue;
        dis[a][b]=dis[b][a]=mn[a][b]=mn[b][a]=c;
    }
    ans=1e8;
    for (int k=1;k<=n;k++)
    {
        for (int i=1;i<k;i++)
        {
            for (int j=1;j<i;j++)
            {
                if (ans<=mn[i][j]+dis[i][k]+dis[k][j]) continue;
                ans=mn[i][j]+dis[i][k]+dis[k][j];
                cnt=0; int now=j;
                while (i-now) rd[++cnt]=now,now=pre[i][now];
                rd[++cnt]=i; rd[++cnt]=k;
            }
        }
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                if (mn[i][j]<=mn[i][k]+mn[k][j]) continue;
                mn[i][j]=mn[i][k]+mn[k][j];
                pre[i][j]=pre[k][j];
            }
        }
    }
    if (ans==1e8) printf("No solution.");
    else for (int i=1;i<=cnt;i++) printf("%d ",rd[i]);
    return 0;
}