「poj 1734」Sightseeing trip (Floyd最小环)

poj 1734
给定一个无向图，求出节点数至少为$3$的最小环。输出方案

当Floyd中最外层循环到$k$，$dis(i,j)$则代表不经过大于等于$k$编号节点的最短路。

所以最小环我们可以枚举必过某个点的最小环是多少。即考虑过$k$点最小环，且只由不大于等于$k$编号节点的点组成。那么最小环即为

$$
\min_{1 \leq i < j < k}(dis(i,j)+a(i,k)+a(k,j))
$$

由于对称性，所以不会影响结果。
输出方案即根据DP转移来回溯答案。具体看代码实现。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int INF = 1000000000;

    int n, m, G[305][305], a[305][305], pre[305][305];

    vector<int > path;

    void getpath(int x, int y) {
        if (!pre[x][y]) return ;
        getpath(x, pre[x][y]);
        path.push_back(pre[x][y]);
        getpath(pre[x][y], y);
    }

    void clean() {
        for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= n; ++j) pre[i][j] = 0, a[i][j] = INF;
        for (int i = 0; i <= n; ++i) a[i][i] = 0;
    }
    int solve() {
        scanf("%d%d", &n, &m);
        clean();
        for (int x, y, v, i = 1; i <= m; ++i) {
            scanf("%d%d%d", &x, &y, &v);
            a[x][y] = a[y][x] = min(a[x][y], v);
        }
        memcpy(G, a, sizeof a);

        int 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)G[i][j] + a[i][k] + a[k][j]) { // 3 个数相加 
                    ans = G[i][j] + a[i][k] + a[k][j];
                    path.clear();
                    path.push_back(i), getpath(i, j), path.push_back(j), path.push_back(k);
                }
            }
            for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                if (G[i][j] > G[i][k] + G[k][j]) {
                    G[i][j] = G[i][k] + G[k][j];
                    pre[i][j] = k;
                }
            }
        }
        if (ans == INF) return printf("No solution.\n"), 0;
        for (int i = 0; i < (int)path.size(); ++i) printf("%d ", path[i]);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}