【題目敘述】https://vjudge.net/problem/HDU-1599
【解題想法】Floyd-Warshall shortest path
#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";
}
}