python/TangDou/Topic/HDU1599.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int INF = 0x3f3f3f3f;
const int N = 110;

int dis[N][N], g[N][N];
int n, m, ans;

void floyd() {
    memcpy(dis, g, sizeof g);
    for (int k = 1; k <= n; k++) {
        // 最小环的DP操作
        for (int i = 1; i < k; i++)         // 枚举i,j
            for (int j = i + 1; j < k; j++) // 注意i,j,k不能相同
                if (ans > dis[i][j] + g[i][k] + g[k][j])
                    ans = dis[i][j] + g[i][k] + g[k][j];

        for (int i = 1; i <= n; i++) // 原floyd
            for (int j = 1; j <= n; j++)
                if (dis[i][j] > dis[i][k] + dis[k][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
    }
}
signed main() {
    while (cin >> n >> m && (~n && ~m)) {
        // 邻接矩阵初始化
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i == j)
                    g[i][j] = 0;
                else
                    g[i][j] = INF;

        while (m--) {
            int a, b, c;
            cin >> a >> b >> c;
            g[a][b] = g[b][a] = min(c, g[a][b]); // 防重边
        }
        ans = INF;
        floyd();
        if (ans == INF)
            puts("It's impossible.");
        else
            cout << ans << endl;
    }
}