【題解】HDU 1599 find the mincost route

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, dis[105][105], a, b, w, g[105][105];

int main() {
    while (cin >> n >> m){
        if (n == 0) break;
        memset(dis, 0x3F, sizeof(dis));
        memset(g, 0x3F, sizeof(g));
        for (int i = 0; i < m; i++){
            cin >> a >> b >> w;
            dis[a][b] = min(w, dis[a][b]);
            dis[b][a] = min(w, dis[b][a]);
            g[a][b] = min(w, g[a][b]);
            g[b][a] = min(w, g[b][a]);
        }
        int ans = 10005;
        for (int k = 1; k <= n; k++){
            for (int i = 1; i <= n; i++){
                if (i == k) continue;
                for (int j = i+1; j <= n; j++){
                    if (j == k) continue;
                    if (g[k][i] < 105 && g[k][j] < 105 && dis[i][j] < 10000){
                        ans = min(ans, g[k][i]+g[k][j]+dis[i][j]);
                    }
                }
            }
            for (int i = 1; i <= n; i++){
                for (int j = 1; j <= n; j++){
                    if (dis[i][k]+dis[k][j] < dis[i][j]) dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
        if (ans == 10005) cout << "It's impossible.\n";
        else cout << ans << "\n";
    }
}