观光之旅

floyd是典型的插点算法，每次插入点k，为此，在点k被[插入前]可计算i-j-k这个环
即此时中间节点为：1~k-1，即我们已经算出了任意i<->j的最短道路，中间经过的节点可以为 (1,2,3,…,k-1)
我们只需枚举所有以k为环中最大节点的环即可。

代码

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std ;
const int N = 110, M = 10010, INF = 0x3f3f3f3f ;
typedef long long LL ;
int g[N][N], d[N][N] ;
int pos[N][N] ;
vector<int> path ;
int n, m ;
void dfs(int i, int j ) {
    int k = pos[i][j] ;
    if (k == 0)    return ;
    dfs(i, k);
    path.push_back(k);
    dfs(k, j);
}
void get_path(int i, int j, int k ) {
    path.clear() ;
    path.push_back(k);
    path.push_back(i);
    dfs(i, j) ;
    path.push_back(j);
}
int main() {
    cin >> n >> m ;
    memset(g, 0x3f, sizeof g) ;
    for (int i = 0 ; i <= n ; i++ )  g[i][i] = 0 ;
    int a, b, c ;
    for (int i = 0 ; i < m ; i++ ) {
        cin >> a >> b >> c ;
        g[a][b] = g[b][a] = min(g[a][b], c) ;
    }
    memcpy(d, g, sizeof d );
    long long res = INF ;
    for (int k = 1 ; k <= n ; k++ ) {
        for (int i = 1 ; i < k ; i++ )
            for (int j = i + 1 ; j < k ; j ++ )
                if (res > (LL)g[i][j] + d[i][k] + d[k][j] ) {
                    res = g[i][j] + d[i][k] + d[k][j] ;
                    get_path(i, j, 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] ;
                    pos[i][j] = k ;
                }
    }
    if (res == INF)
        cout << "No solution." << endl;
    else {
        for (auto x : path)
            cout << x << ' ' ;
        cout << endl;
    }
    return 0;
}