题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4034
题目分类:图论
题意:n个顶点,然后给出从i到j的最短路径长度,求至少需要哪些边
第二组样例
第三组样例:
题目分析:
判断 a[i][j]==a[i][k]+a[k][j](详看代码)
代码:
#include<bits/stdc++.h>using namespace std;int a[][];int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif int t,n;
scanf("%d",&t);
for(int kase=;kase<=t;kase++)
{
scanf("%d",&n);
memset(a,,sizeof(a));
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
bool ok=;
int ans=;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
for(int k=;k<=n;k++)
{
if(i==k||k==j||i==j)
continue;
if(a[i][j]>a[i][k]+a[k][j])
{
ok=;
goto here;
}
else if(a[i][j]==a[i][k]+a[k][j])
{
//printf("%d %d\n",i,j);
ans++;
break;
}
}
}
}
here:
printf("Case %d: ",kase);
if(ok) printf("impossible\n");
else printf("%d\n",n*n-n-ans); } return ;
}