poj 2139 最短路

传送门

题意：牛拍电影，牛到自己距离是0，如果两只牛合作过一部电影，那么他们距离为1，如果俩牛没一起过，但他们都和另一只牛合作过，那么他们距离为2，以此类推，问到其他牛的平均距离最小的是多少。

思路：根据提议，建立二维数组储存牛的距离，再floyd一边，再算平均距离最小的，这里平均距离输出时乘以100输出。

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1<<29
using namespace std;
int n,m,a[305][305],k,b[305];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)a[i][j]=maxn;
a[i][i]=0;
}
for(int i=0;i<m;i++)
{
scanf("%d",&k);
for(int j=1;j<=k;j++)
{
scanf("%d",&b[j]);
}
for(int x=1;x<=k;x++)
{
for(int y=x+1;y<=k;y++)
{
a[b[x]][b[y]]=a[b[y]][b[x]]=1;
}
}
}
for(int x=1;x<=n;x++)
{
for(int y=1;y<=n;y++)
{
for(int z=1;z<=n;z++)
{
if(a[y][z]>a[y][x]+a[x][z])
{
a[y][z]=a[y][x]+a[x][z];
}
}
}
}
int ma=maxn;
int sum;
for(int i=1;i<=n;i++)
{
sum=0;
for(int j=1;j<=n;j++)
{
sum+=a[i][j];
}
if(sum<ma)ma=sum;
}
cout<<ma*100/(n-1)<<endl;
return 0;
}

最后

以上就是彩色黑猫为你收集整理的poj 2139 最短路的全部内容，希望文章能够帮你解决poj 2139 最短路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。