poj 2139 最短路

92 阅读 0 评论 61 点赞

我是靠谱客的博主彩色黑猫，这篇文章主要介绍poj 2139 最短路，现在分享给大家，希望可以做个参考。

传送门

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

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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;
}