题意：给定原图顶点间的最短路，问原图最少有几条边。
分析：若两点的距离可由另外两条边来代替，则可删去该边；若存在比这两点的距离更短的路径，则“impossible”.
View Code
1 /* 2 Author:Zhaofa Fang 3 Lang:C++ 4 */ 5 #include <cstdio> 6 #include <cstdlib> 7 #include <iostream> 8 #include <cmath> 9 #include <cstring> 10 #include <algorithm> 11 #include <string> 12 #include <utility> 13 #include <vector> 14 #include <queue> 15 #include <stack> 16 #include <map> 17 #include <set> 18 using namespace std; 19 typedef long long ll; 20 #define pii pair<int,int> 21 #define pb push_back 22 #define mp make_pair 23 #define fi first 24 #define se second 25 #define lowbit(x) (x&(-x)) 26 const int INF = 2147483647; 27 28 int maz[105][105]; 29 int floyd(int n) 30 { 31 int cnt = 0; 32 for(int k=0;k<n;k++) 33 { 34 for(int i=0;i<n;i++) 35 { 36 for(int j=0;j<n;j++) 37 { 38 if(i == k || j == k || i == k)continue; 39 if(maz[i][k] == -1 || maz[k][j] == -1 || maz[i][j] == -1)continue; 40 if(maz[i][j] > maz[i][k] + maz[k][j])return -1; 41 if(maz[i][j] == maz[i][k] + maz[k][j]) 42 { 43 cnt++;maz[i][j]=-1; 44 } 45 } 46 } 47 } 48 return n*(n-1) - cnt ; 49 } 50 int main() 51 { 52 #ifndef ONLINE_JUDGE 53 freopen("in","r",stdin); 54 #endif 55 int T,cas=0; 56 scanf("%d",&T); 57 while(T--) 58 { 59 int n; 60 scanf("%d",&n); 61 memset(maz,0,sizeof(maz)); 62 for(int i=0;i<n;i++) 63 for(int j=0;j<n;j++) 64 scanf("%d",&maz[i][j]); 65 int tmp = floyd(n); 66 printf("Case %d: ",++cas); 67 if(tmp != -1)printf("%d\n",tmp); 68 else puts("impossible"); 69 } 70 return 0; 71 }