AcWing 4475. 大众情人-yxc版
原题链接
中等
作者:
lingye
,
2024-04-08 21:11:28
,
所有人可见
,
阅读 17
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n;
char sex[N];
int g[N][N];
int main()
{
memset(g, 0x3f, sizeof g);
cin >> n;
for (int i = 1; i <= n; i ++ )
{
g[i][i] = 0;
char s[2]; int k;
scanf("%s%d", s, &k);
sex[i] = s[0];
for (int j = 0; j < k; j ++ )
{
int a, d; char c;
cin >> a >> c >> d;
g[i][a] = d;
}
}
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
for (auto c: string("FM"))
{
int mn = INF;
for (int i = 1; i <= n; i ++ )
if (sex[i] == c)
{
int mx = 0;
for (int j = 1; j <= n; j ++ )
if (sex[i] != sex[j])
mx = max(mx, g[j][i]);
mn = min(mn, mx);
}
for (int i = 1; i <= n; i ++ )
if (sex[i] == c)
{
int mx = 0;
for (int j = 1; j <= n; j ++ )
if (sex[i] != sex[j])
mx = max(mx, g[j][i]);
if (mx == mn) printf("%d ", i);
}
puts("");
}
return 0;
}