floy求最短距离
最短距离找最大 代表当前人的 异性缘
然后继续在 最大当中找最小 因为异性缘是1/max dis
max dis 越小 异性缘越大
有很多方式
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <math.h>
#include <string>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
#include <set>
#include <list>
#include <iostream>
using namespace std;
//map<string,string>ip;
//map<string,bool>cy;
typedef long long ll;
const int maxn=500+188;
const ll inf=1e10;
ll n,m,k,flag,cnt,sum;
ll d[1000];
ll g[555][505];
int p[1000];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) {
if(i==j) g[i][j]=0;
else g[i][j]=inf;
}
}
for(int i=1;i<=n;i++){
char ch; cin>>ch;
if(ch=='M') p[i]=1;
cin>>k;
for(int j=1;j<=k;j++){
int nm,l;
scanf("%d:%d",&nm,&l);
g[nm][i]=l;
}
}
// Floyd
memset(d,-1,sizeof(d));
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++){
if(g[i][j]>g[i][k]+g[k][j]) g[i][j]=g[i][k]+g[k][j];
}
}
}
ll mav=100000000000;
ll man=100000000000;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) continue;
if(p[i]==0&&p[j]==1) d[i]=max(d[i],g[i][j]);
if(p[i]==1&&p[j]==0) d[i]=max(d[i],g[i][j]);
}
if(d[i]==-1) continue;
if(p[i]) man=min(man,d[i]);
else mav=min(mav,d[i]);
/// cout<<d[i]<<endl;
}
// cout<<g[4][1]<<endl;
int flag=0;
for(int i=1;i<=n;i++){
if(p[i]==0&&d[i]==mav) {
if(flag) cout<<" ";
cout<<i;flag=1;
}
}
cout<<endl;
flag=0;
for(int i=1;i<=n;i++){
if(p[i]==1&&d[i]==man) {
if(flag) cout<<" ";
cout<<i;flag=1;
}
}
//cout<<endl;
return 0;
}
