2022 团体程序设计天梯赛 L2-4

题意

1. 给定每个人和其他人的距离
2. 没有直接连接的两人的距离是二者的最短路径长度
3. 没有连接的两人不做考虑
4. 一个人的受欢迎度是1/所有异性到ta的最大距离
5. 求男性最受欢迎的人的编号，和女性最受欢迎的人的编号

思路

1. floyd求最短路
2. 模拟

本题难度在于恶臭的阅读理解

solution

这份代码是赛后完成的，且现在没有开放补题，不能保证完全通过。

upd 2022年5月2日 已通过全部测试用例

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> vi;
const int N = 507;
const int INF = 0x3f3f3f3f;
int a[N];
bool male[N];

int g[N][N];
void out(vector<int> a) {
    for (int i = 0, n = a.size(); i < n; ++i) {
        cout << a[i] << (i == n - 1 ? '\n' : ' ');
    }
}
signed main() {
    int n;
    cin >> n;
    cin.ignore();
    rep(i, 1, n) a[i] = -1;
    rep(i, 1, n) rep(j, 1, n) if (i != j) g[i][j] = INF;
    rep(j, 1, n) {
        string sex;
        cin >> sex;
        if (sex == "M") male[j] = 1;
        int k, x, s;
        cin >> k;
        rep(i, 1, k) {
            cin >> x;
            cin.ignore();
            cin >> s;
            g[j][x] = s;
        }
    }

    rep(k, 1, n) rep(x, 1, n) rep(y, 1, n) {
        g[x][y] = min(g[x][y], g[x][k] + g[k][y]);
    }

    rep(i, 1, n) rep(j, 1, n) if (male[i] != male[j]) a[i] = max(a[i], g[j][i]);

    int maleMin = INF, femaleMin = INF;
    rep(i, 1, n) {
        if (a[i] != -1) {
            if (male[i])
                maleMin = min(maleMin, a[i]);
            else
                femaleMin = min(femaleMin, a[i]);
        }
    }
    vi resM, resF;
    rep(i, 1, n) {
        if (male[i] && a[i] == maleMin) resM.push_back(i);
        if (!male[i] && a[i] == femaleMin) resF.push_back(i);
    }
    out(resF);
    out(resM);

    return 0;
}
/*
6
F 1 4:1
F 2 1:3 4:10
F 2 4:2 2:2
M 2 5:1 3:2
M 2 2:2 6:2
M 2 3:1 2:5
2 3
4
*/