原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=4034
题意：
给你一个最短路的表，让你还原整个图，并使得边最少
题解：
这样想。。这个表示通过floyd得到的，那么如果从u到v没有小于等于边(u,v)的路径，那么边(u,v)就是必须的，否则从u到v需要走更远的路。如果有路径和边(u,v)是一样的，那么边(u,v)就是不需要的，这是因为，任何需要从u到v的路径都可以用另外一条代替。如果有小于边(u,v)的，那么这就是个非法的最短路表。
代码：
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cstdio>
#define MAX_N 103
#define INF 50000000
using namespace std; int T;
int N; int d[MAX_N][MAX_N]; struct edge {
public:
int u, v, c; edge(int uu, int vv, int cc) : u(uu), v(vv), c(cc) { } edge() { }
}; edge E[MAX_N*MAX_N];
int tot=; int main() {
scanf("%d", &T);
int cas = ;
while (T--) {
tot = ;
scanf("%d", &N);
for (int i = ; i < N; i++)
for (int j = ; j < N; j++) {
scanf("%d", &d[i][j]);
if (i != j)E[tot++] = edge(i, j, d[i][j]);
}
int cnt = tot;
bool flag = true;
for (int i = ; i < tot; i++) {
int u = E[i].u, v = E[i].v, c = E[i].c;
int tmp = INF;
for (int j = ; j < N; j++)
if (j != u && j != v)
tmp = min(tmp, d[u][j] + d[j][v]);
if (tmp > d[u][v])continue;
if (tmp < d[u][v]) {
flag = false;
break;
}
cnt--;
}
printf("Case %d: ", ++cas);
if (flag)
printf("%d\n", cnt);
else
printf("impossible\n");
}
return ;
}