P6175 无向图的最小环问题

#include<bits/stdc++.h>
using namespace std;
const int MAXn = 1e2;
const int INF = 0x20202020;

template <typename T> 
inline void read(T &a) {
    register char c;while (c = getchar(), c < '0' || c > '9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);}a = x;  
}
template <typename T, typename ...Argv>
inline void read(T &n, Argv &...argv) {
    read(n), read(argv...);
}

int n, m, ans = INF;
int wei[MAXn + 10][MAXn + 10], dis[MAXn + 10][MAXn + 10];
signed main() {
    read(n, m);
    memset(wei, 0x20, sizeof(wei));
    memset(dis, 0x20, sizeof(dis));
    for (int i = 1; i <= n; ++i) {
        wei[i][i] = dis[i][i] = 0;
    }
    for (int i = 1, u, v, w; i <= m; ++i) {
        read(u, v, w);
        wei[u][v] = wei[v][u] = dis[u][v] = dis[v][u] = min(dis[u][v], w);
    }
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i == j || j == k || k == i) continue;
                ans = min(ans, wei[i][k] + wei[k][j] + dis[j][i]);
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    if (ans == INF) {
        printf("No solution.\n");
    } else {
        printf("%d\n", ans);
    }
}```