天梯赛_L2-044 大众情人(floyd)

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 510, INF = 0x3f3f3f3f;
bool sx[N]; // 性别，0:female, 1:male
int g[N][N];    // 邻接矩阵
int resf[N], resm[N], cntf, cntm;
void floyd(){
    for(int k = 1; k <= n; k ++){
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= n; j ++){
                if(i != j) g[i][j] = min(g[i][k] + g[k][j], g[i][j]);
            }
        }
    }
}
int main(){
    memset(g, 0x3f3f, sizeof g);
    scanf("%d\n", &n);
    for(int i = 1; i <= n; i ++){
        char ch;
        int k;
        scanf("%c %d", &ch, &k);
        if(ch == 'M') sx[i] = true;
        for(int j = 1; j <= k; j ++){
            int id, dist;
            scanf("%d:%d", &id, &dist);
            g[i][id] = dist;
        }
        getchar();
    }
    
    floyd();
    
    int minmaxm2f = INF, minmaxf2m = INF;
    for(int i = 1; i <= n; i ++){   // 遍历所有人
        if(sx[i]){  // male
            int maxe = -1;
            for(int j = 1; j <= n; j ++) if(!sx[j] && g[j][i] > maxe) maxe = g[j][i];
            if(maxe < minmaxf2m) minmaxf2m = maxe, resm[cntm = 1] = i;
            else if(maxe == minmaxf2m) resm[++ cntm] = i;
        }
        else{   // female
            int maxe = -1;
            for(int j = 1; j <= n; j ++) if(sx[j] && g[j][i] > maxe) maxe = g[j][i];
            if(maxe < minmaxm2f) minmaxm2f = maxe, resf[cntf = 1] = i;
            else if(maxe == minmaxm2f) resf[++ cntf] = i;
        }
    }
    for(int i = 1; i <= cntf; i ++) cout << resf[i] << " \n"[i == cntf];
    for(int i = 1; i <= cntm; i ++) cout << resm[i] << " \n"[i == cntm];
    return 0;
}