1. 大众情人

大众情人

#include<bits/stdc++.h> 
using namespace std;
const int maxn=500+10; 
typedef long long ll; 
const ll INF=1e10+5;

vector<int> F,M,ans;
int n,m,k;
ll room[maxn][maxn];
char sex;
int check(int x){
//  if(F.count==1)
}
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(room[i][j]>room[i][k]+room[k][j]&&i!=j){
                    room[i][j]=room[i][k]+room[k][j];
                }
            }
        }
    }
} 
void init(){
    for(int i=0;i<maxn;i++){
        for(int j=0;j<maxn;j++){
            if(i==j) room[i][j]=INF;else room[i][j]=INF;
        } 
    } 
}
int main()
{
    cin>>n;
    init();

    for(int i=1;i<=n;i++){
        getchar();
        scanf("%c %d",&sex,&m);
        if(sex=='F') F.push_back(i);else M.push_back(i);
        for(int j=0;j<m;j++){
            int b,c;
            scanf("%d:%d",&b,&c);
            if(room[i][b]>c) room[i][b]=c;//判重！！！--马上可以写。 
//          if(room[b][i]>c) room[b][i]=c;//忘记是无向边了。 
        }
    }
//  
    floyd();
//      for(int i=1;i<=n;i++){
//      for(int j=1;j<=n;j++){
//          cout<<room[i][j]<<" ";
//      }
//      puts("");
//  }
    //多起点找每个终点就是跑一遍。 
    ll minn=INF;//minn表示前F[i]个到每个终点最大值的最小值是多少。 
    for(int i=0;i<F.size();i++){
        ll ma=-1;//-1有没有关系??? 
        for(int j=0;j<M.size();j++){
            if(room[M[j]][F[i]]>ma){
                ma=room[M[j]][F[i]];
            }
        }

//      cout<<"??????"<<ma<<endl;
        if(minn>ma){
            ans.clear();
//          cout<<"!!!!!"<<F[i]<<endl;
            ans.push_back(F[i]);
            minn=ma;
        }else if(minn==ma){
            ans.push_back(F[i]);
        }
    }
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++){
        if(i==0) printf("%d",ans[i]);else printf(" %d",ans[i]);
    } 
    puts(""); 
//====================分割线==========================

    minn=INF;//minn表示前F[i]个到每个终点最大值的最小值是多少。 
    for(int i=0;i<M.size();i++){
        int ma=-1;//-1有没有关系??? 
        for(int j=0;j<F.size();j++){
            if(room[F[j]][M[i]]>ma){
                ma=room[F[j]][M[i]];
            }
        }


        if(minn>ma){
            ans.clear();
            ans.push_back(M[i]);
            minn=ma;
        }else if(minn==ma){
            ans.push_back(M[i]);
        }
    }
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++){
        if(i==0) printf("%d",ans[i]);else printf(" %d",ans[i]);
    }  


    return 0;
}