【题意】：一个有向图，给出每两点之间的最短路，问原图至少有多少条边？

【题解】：做一次floyd，记录哪些边可以由其他边来代替，那么这些边都是可以去掉的。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 #define maxn 105
 6 int maz[maxn][maxn], maz1[maxn][maxn];
 7 bool visit[maxn][maxn];
 8 int n;
 9 
10 int solve() {
11     int cnt = 0;
12     memset(visit, false, sizeof(visit));
13     for(int k = 0; k < n; k++)
14         for(int i = 0; i < n; i++)
15             if(i != k)
16                 for(int j = 0; j < n; j++)
17                     if(j != k) {
18                         if(maz[i][j] == maz[i][k] + maz[k][j] && !visit[i][j]) cnt++, visit[i][j] = true;
19                         if(maz[i][j] > maz[i][k] + maz[k][j]) return -1;
20                     }
21     return n * (n - 1) - cnt;
22 }
23 
24 int main() {
25     int T, tt = 1;
26     scanf("%d", &T);
27     while(T--) {
28         scanf("%d", &n);
29         for(int i = 0; i < n; i++)
30             for(int j = 0; j < n; j++)
31                 scanf("%d", &maz[i][j]);
32         int ans = solve();
33         printf("Case %d: ", tt++);
34         if(ans == -1) printf("impossible\n");
35         else printf("%d\n", ans);
36     }
37     return 0;
38 }