昨天成都网赛的题，我后面接队友手读的，看到数据规模N<=100，瞬间想到了floyd，想了下，果然是floyd的变种，敲完后，WA了俩次，然后AC。。。
#include <stdio.h>
#include <string.h>
int ncase, n;
int map[110][110];
int sign[110][110];
void floyd()
{
int i, j, k;
for ( k = 0 ; k < n ; k++ )
for ( i = 0 ; i < n ; i++ )
for ( j = 0 ; j < n ; j++ )
if ( i != j && j!=k && i!=k )
if ( map[i][j] == map[i][k]+map[k][j] ) {
sign[i][j] = 1;
}
}
int judge()
{
int i, j, k;
for ( k = 0 ; k < n ; k++ )
for ( i = 0 ; i < n ; i++ )
for ( j = 0 ; j < n ; j++ )
if ( map[i][j] > map[i][k]+map[k][j] )
return 1;
return 0;
}
int main()
{
scanf("%d", &ncase);
int i, j, k;
for ( k = 1 ; k <= ncase ; k++ )
{
scanf("%d", &n);
for ( i = 0 ; i < n ; i++ )
for ( j = 0 ; j < n ; j++ )
scanf("%d", map[i]+j);
printf("Case %d: ", k);
memset(sign, 0, sizeof(sign));
if (judge())
printf("impossible\n");
else
{
floyd();
int num= 0;
for ( i = 0 ; i < n ; i++ ) {
for ( j = 0 ; j < n ; j++ ) {
if (!sign[i][j] && map[i][j]) {
num++;
}
}
}
printf("%d\n", num);
}
}
return 0;
}