思路与算法

重边只留最小权。按k递增执行Floyd，但在加入中转点k之前，枚举i<j<k，检查d[i][j]+w[i][k]+w[j][k]，保存最小候选及Floyd中转表恢复出的i到j路径，最后加k。无候选则输出No solution.。

正确性说明

任一至少3点的简单环有唯一最大编号k。删去k及相邻两边后得到只用编号小于k的i到j路径；Floyd此时的d[i][j]不大于该路径长度。因此枚举不会错过全局最小环。候选路径的内部顶点均小于k，不含k；正权最短路可以取简单路，连回k构成合法环。所有候选都是合法环，最小值因此准确。保存改进时的中转路径避免之后Floyd更新改变方案。

复杂度

O(n³D+mD)时间、O(n²D)空间，D为路径和位数；包括矩阵可达性、权重和中转表初始化。

易错点

必须先检查环，再允许k作为中转点。两条平行边不算至少3点的环，自环也不能充数。输出任何最小环均可，特判核对点互异、所有边存在及独立最优费用。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct cpp_int {
    string s;
    bool neg;
    cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
        if (neg)
            s.erase(s.begin());
    }
    void norm() {
        auto p = s.find_first_not_of('0');
        s = p == string::npos ? "0" : s.substr(p);
        if (s == "0")
            neg = false;
    }
    static int cmpabs(const cpp_int &a, const cpp_int &b) {
        if (a.s.size() != b.s.size())
            return a.s.size() < b.s.size() ? -1 : 1;
        return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
    }
    friend bool operator<(const cpp_int &a, const cpp_int &b) {
        if (a.neg != b.neg)
            return a.neg;
        int c = cmpabs(a, b);
        return a.neg ? c > 0 : c < 0;
    }
    friend bool operator==(const cpp_int &a, const cpp_int &b) {
        return a.neg == b.neg && a.s == b.s;
    }
    friend bool operator!=(const cpp_int &a, const cpp_int &b) {
        return !(a == b);
    }
    friend bool operator>(const cpp_int &a, const cpp_int &b) {
        return b < a;
    }
    friend bool operator<=(const cpp_int &a, const cpp_int &b) {
        return !(b < a);
    }
    friend bool operator>=(const cpp_int &a, const cpp_int &b) {
        return !(a < b);
    }
    cpp_int operator-() const {
        cpp_int r = *this;
        if (r.s != "0")
            r.neg = !r.neg;
        return r;
    }
    friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
        cpp_int r;
        r.s.clear();
        int carry = 0;
        if (a.neg == b.neg) {
            int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                r.s += char('0' + v % 10);
                carry = v / 10;
            }
            r.neg = a.neg;
        } else {
            const cpp_int *x = &a, *y = &b;
            if (cmpabs(a, b) < 0)
                swap(x, y);
            int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
            while (i >= 0) {
                int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                carry = v < 0;
                if (carry)
                    v += 10;
                r.s += char('0' + v);
            }
            r.neg = x->neg;
        }
        reverse(r.s.begin(), r.s.end());
        r.norm();
        return r;
    }
    friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
        return a + (-b);
    }
    friend cpp_int operator*(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long carry = 0;
        long long z = b;
        if (z < 0)
            z = -z;
        for (int i = (int)a.s.size() - 1; i >= 0; i--) {
            carry += (a.s[i] - '0') * z;
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        while (carry) {
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        reverse(r.s.begin(), r.s.end());
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    friend cpp_int operator/(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long rem = 0, z = b;
        if (z < 0)
            z = -z;
        for (char c : a.s) {
            rem = rem * 10 + c - '0';
            r.s += char('0' + rem / z);
            rem %= z;
        }
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    cpp_int &operator+=(const cpp_int &b) {
        *this = *this + b;
        return *this;
    }
    cpp_int &operator-=(const cpp_int &b) {
        *this = *this - b;
        return *this;
    }
    cpp_int &operator*=(int b) {
        *this = *this * b;
        return *this;
    }
    friend istream &operator>>(istream &in, cpp_int &a) {
        string v;
        if (in >> v) {
            a.neg = v[0] == '-';
            if (v[0] == '-' || v[0] == '+')
                v.erase(v.begin());
            a.s = v;
            a.norm();
        }
        return in;
    }
    friend ostream &operator<<(ostream &out, const cpp_int &a) {
        if (a.neg)
            out << '-';
        return out << a.s;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<cpp_int>> g(n, vector<cpp_int>(n)), d = g;
    vector<vector<int>> has(n, vector<int>(n)), ok = has, mid(n, vector<int>(n, -1));
    for (int i = 0; i < n; i++)
        ok[i][i] = 1;
    while (m--) {
        int u, v;
        cpp_int w;
        cin >> u >> v >> w;
        --u;
        --v;
        if (u == v)
            continue;
        if (!has[u][v] || w < g[u][v]) {
            g[u][v] = g[v][u] = w;
            d[u][v] = d[v][u] = w;
            has[u][v] = has[v][u] = ok[u][v] = ok[v][u] = 1;
        }
    }
    bool found = false;
    cpp_int best;
    vector<int> ans;
    function<void(int, int, vector<int> &)> path = [&](int a, int b, vector<int> &v) {
        int k = mid[a][b];
        if (k < 0) {
            v.push_back(a);
            return;
        }
        path(a, k, v);
        path(k, b, v);
    };
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < k; i++)
            for (int j = i + 1; j < k; j++)
                if (ok[i][j] && has[i][k] && has[j][k]) {
                    cpp_int value = d[i][j] + g[i][k] + g[j][k];
                    if (!found || value < best) {
                        found = true;
                        best = value;
                        ans.clear();
                        path(i, j, ans);
                        ans.push_back(j);
                        ans.push_back(k);
                    }
                }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (ok[i][k] && ok[k][j]) {
                    cpp_int v = d[i][k] + d[k][j];
                    if (!ok[i][j] || v < d[i][j]) {
                        d[i][j] = v;
                        ok[i][j] = 1;
                        mid[i][j] = k;
                    }
                }
    }
    if (!found)
        cout << "No solution.\n";
    else {
        for (int v : ans)
            cout << v + 1 << " ";
        cout << "\n";
    }
}