题解 - P10927 Sightseeing trip

## 思路

抽象题意：

> 给定 $N$ 个点，$M$ 条无向边，求最小环。

首先发现 $N$ 很小，所以可以用 Floyd。

设原图为 $g$，最短路为 $d$。

考虑如果当前的中间点为 $k$，要更新的最短路的起点为 $i$，终点为 $k$，在还没有更新所有以 $k$ 为中间点的最短路时，其他最短路是不会经过 $k$ 的，所以就形成了一个 $i \to j \to k \to i$ 的环，然后取最小值就可以的到答案了。

然后思考如何求出路径。

可以用 $path$ 记录路径，那么在更新最小环时可以先放入 $k$，再放入 $i$，再放入 $i$ 到 $j$ 的路径，最后再放入 $j$。

现在的问题是如何求出 $i$ 到 $j$ 的路径。

可以设计一个函数 $get\_path(i, j)$。

为了方便实现，再定义一个数组 $mid_{i, j}$ 表示 $i$ 到 $j$ 的中间点，可以在 Floyd 的过程中求。

那么我们就可已得到函数：

```cpp
void get_path(int i, int j) {
    if (!mid[i][j])
        return;
    
    int k = mid[i][j];
    get_path(i, k);
    path[ ++ cnt] = k;
    get_path(k, j);
}
```

最后在把 $path$ 输出即可。

## 代码

C++ 代码如下：

```cpp
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 105;
const int inf = 0x3f3f3f3f;

int n, m;
int g[N][N];
int d[N][N];
int mid[N][N];
int cnt, path[N];
int ans;

void get_path(int i, int j) {
    if (!mid[i][j])
        return;
    
    int k = mid[i][j];
    get_path(i, k);
    path[ ++ cnt] = k;
    get_path(k, j);
}

void inp() {
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);

while (m -- ) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);

if (w < g[u][v])
            g[u][v] = g[v][u] = w;
    }
}

void work() {
    memcpy(d, g, sizeof g);
    ans = inf;

for (int k = 1; k <= n; k ++ ) {
        for (int i = 1; i < k; i ++ )
            for (int j = i + 1; j < k; j ++ )
                if (ans > (LL)d[i][j] + g[i][k] + g[k][j]) {
                    ans = d[i][j] + g[i][k] + g[k][j];
                    cnt = 0;
                    path[ ++ cnt] = k;
                    path[ ++ cnt] = i;
                    get_path(i, j);
                    path[ ++ cnt] = j;
                }

for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    mid[i][j] = k;
                }
    }

if (ans == inf)
        puts("No solution.");
    else {
        for (int i = 1; i <= cnt; i ++ ) {
            printf("%d", path[i]);

if (i < cnt)
                putchar(' ');
        }
    }
}

int main() {
    inp();
    work();

return 0;
}
```