大众情人

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int dist[N][N], n;
char gender[N];
int main()
{
    scanf("%d", &n);
    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= n; i ++) dist[i][i] = 0;
    for (int i = 1; i <= n; i ++)
    {
        char s[2];
        int cnt;
        scanf("%s %d", s, &cnt);
        gender[i] = s[0];
        for (int j = 1; j <= cnt; j ++)
        {
            int id, distance;
            scanf("%d:%d", &id, &distance);
            dist[i][id] = distance;
        }
    }
    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    for (auto item : string("FM"))
    {
        int minx = 0x3f3f3f3f;
        for (int i = 1; i <= n; i ++)
        {
            if (gender[i] == item)
            {
                int maxx = 0;
                for (int j = 1; j <= n; j ++)
                {
                    if (gender[i] != gender[j])
                        maxx = max(dist[j][i], maxx);
                }
                minx = min(minx, maxx);
            }
        }

        for (int i = 1; i <= n; i ++)
        {
            if (gender[i] == item)
            {
                int maxx = 0;
                for (int j = 1; j <= n; j ++)
                {
                    if (gender[i] != gender[j])
                        maxx = max(dist[j][i], maxx);
                }
                if(maxx == minx) printf("%d ", i);
            }
        }
        puts("");
    }
    return 0;
}