题面
人与人之间总有一点距离感。
我们假定两个人之间的亲密程度跟他们之间的距离感成反比，并且距离感是单向的。
例如小蓝对小红患了单相思，从小蓝的眼中看去，他和小红之间的距离为 \(1\)，只差一层窗户纸；但在小红的眼里，她和小蓝之间的距离为 \(108000\)，差了十万八千里…… 另外，我们进一步假定，距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为 \(2\)，则即使小绿并不直接认识小红，我们也默认小绿早晚会认识小红，并且因为跟小蓝很亲近的关系，小绿会觉得自己跟小红之间的距离为 \(1+2=3\)。
当然这带来一个问题，如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？
我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。
一个人的异性缘不是由最喜欢他/她的那个异性决定的，而是由对他/她最无感的那个异性决定的。
我们记一个人 \(j\) 在一个异性 \(j\) 眼中的距离感为 \(D_{ij}\)；将 \(i\) 的“异性缘”定义为 \(1/max_{j\in s(i)}{D_{ij}}\) 。
其中 \(S(i)\) 是相对于 \(i\) 的所有异性的集合。那么“大众情人”就是异性缘最好（值最大）的那个人。
本题就请你从给定的一批人与人之间的距离感中分别找出两个性别中的“大众情人”。
Input
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
Ouput
2 3
4
Solution
义眼丁真。
再看一眼数据范围，显然确实是全源最短路径。
\(Floyd\) ？？
\(n^3\) 跑 \(400ms\) ？
尊嘟假嘟？\(o.0\)
暴力 \(dj\) ？
\(n^2logn\) 天才！
于是最后一个点死活 \(T\) 死。。。
考完才幡然醒悟 \(dj\) 时间复杂度是 \((n+m)logn\)。
而且这是稠密图。
总时间复杂度比 \(Floyd\) 还高，还有大常数。
确实忘太多了。
还有真受不了 \(pta\) 各种奇怪的卡空格和回车。。。
Code
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 505;
int n, sex[N], dis[N][N], vis[N], Max[N], res1[N], res2[N], tot1, tot2;
char s[5];
inline void read(int &x) {
x = 0; int f = 1, c = getchar();
for(; !isdigit(c); c = getchar())
if(c == '-') f = -1;
for(; isdigit(c); c = getchar())
x = x * 10 + c - 48;
x *= f;
}
int main() {
memset(dis, 0x3f, sizeof dis);
read(n);
for(int i = 1, k; i <= n; i++) {
scanf("%s", s);
if(s[0] == 'F') sex[i] = 1; // 女
else sex[i] = 2; // 男
read(k);
for(int j = 1, x, y; j <= k; j++) {
read(x), read(y);
dis[i][x] = y;
}
}
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(sex[j] != sex[i]) Max[i] = max(Max[i], dis[j][i]);
res1[0] = res2[0] = 0x3f3f3f3f;
for(int i = 1; i <= n; i++) {
if(sex[i] == 1) res1[0] = min(res1[0], Max[i]);
else res2[0] = min(res2[0], Max[i]);
}
for(int i = 1; i <= n; i++)
if(sex[i] == 1 && Max[i] == res1[0]) res1[++ tot1] = i;
for(int i = 1; i <= n; i++)
if(sex[i] == 2 && Max[i] == res2[0]) res2[++ tot2] = i;
for(int i = 1; i <= tot1; i++) {
printf("%d", res1[i]);
if(i < tot1) putchar(' ');
} putchar('\n');
for(int i = 1; i <= tot2; i++) {
printf("%d", res2[i]);
if(i < tot2) putchar(' ');
} putchar('\n');
return 0;
}