题目描述：
相信大家都会解决有向图的最短路问题。这次我们反着来，给你一个有向图中每一对顶点之间的最短路的长度，请你计算出原图中最少可能包含多少条边。
输入：
输入的第一行是一个整数T（T<=10），表示有T组测试数据。
每组输入的第一行是一个整数N（1<=N<=100），表示顶点个数。
接下来N行，每行输入N个整数，这些整数都小于10000。
第i行的第j个整数表示从顶点i到顶点j的最短路的长度。
第i行的第i个数字一定是0，其他的数字都大于0。
输出：
对于每组输入，先输出“Case k: ”，k表示样例的序号，从1开始。然后输出一个整数，表示原图中最少可能包含多少条边。如果原图不存在，则输出“impossible”（引号不输出）。
样例输入：
3
3
0 1 1
1 0 1
1 1 0
3
0 1 3
4 0 2
7 3 0
3
0 1 4
1 0 2
4 2 0
样例输出：
Case 1: 6
Case 2: 4
Case 3: impossible
解题思路：
这道题主要就是Floyd，用Floyd跑一遍，然后最短路径也就是dir[i][j]==dir[i][k]+dir[k][j]；说明这条路是多余的，将它标记出来，减去这条路，如果是dir[i][j]>dir[i][k]+dir[k][j]，说明还有新的最短路，不符合题意，所以就是不存在。
程序代码：
#include<stdio.h> #include<string.h> #define N 110 int main() { int t,i,j,k,ans,n,flag,num=0; int dir[N][N]; scanf("%d",&t); while(t--) { num++; flag=0; scanf("%d",&n); memset(dir,0,sizeof(dir)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&dir[i][j]); ans=n*2; for(k=1;k<=n;k++) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i==j||i==k||j==k) continue; if(dir[i][j]!=-1&&dir[i][k]!=-1&&dir[k][j]!=-1) { if(dir[i][j]==dir[i][k]+dir[k][j]) { dir[i][j]=-1; ans--; } if(dir[i][j]>dir[i][k]+dir[k][j]) flag=1; } } } } if(flag==1) printf("Case %d: impossible\n",num); else printf("Case %d: %d\n",num,ans); } return 0; }
