L2-4 大众情人

**

题意：每两个人眼中之间的距离是不相同的，现在有n个，找出其他异性人中对他的最远距离，然后分别在男性和女性中找出最小的《最远距离》。可以有多个人。

题解： 用floyd算法，多源汇最短路。求出每个人间的最短距离，然后对每个人进行遍历，找出该人的最远距离。然后再遍历一次找出最小值。输出。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 550;
int g[N][N];
int d[N];
int sex[N];

int main()
{
	int n;
	cin>>n;
	memset(g,0x3f,sizeof g);//用floyd时一定要初始化
	for(int i=1;i<=n;i++)g[i][i]=0; //可有可无
	
	for(int i=1;i<=n;i++){
		char c;int k;
		scanf(" %c %d",&c,&k);
		if(c=='F')sex[i]=1;//nv
		else sex[i] = 2;//nan
		
		while(k--){
			int b,c;
			scanf("%d:%d",&b,&c);
			g[i][b] = c;
		}
	}
	
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
			}
		}
	}
	
	//异性缘为女到男最大的距离分之一
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(sex[i]!=sex[j])
				d[i] = max(d[i],g[j][i]);
		}
	} 
	
	
	int d1 = 0x3f3f3f3f,d2=0x3f3f3f3f;//d1 nan d2 nv
	for(int i=1;i<=n;i++){
		if(sex[i]==1)d2 = min(d2,d[i]);
		else d1 = min(d1,d[i]);
	}
	
	vector<int> a,b;
	
	for(int i=1;i<=n;i++)
	{
		if(d[i]==d1 && sex[i]==2)
			b.push_back(i);
		else if(d[i]==d2 && sex[i]==1 )
			a.push_back(i);
	}
	cout<<a[0];
	for(int i=1;i<a.size();i++)
		cout<<" "<<a[i];
		
	cout<<endl<<b[0];
	for(int i=1;i<b.size();i++)
		cout<<" "<<b[i];
		
	
	
	
}