突然发现所有的题解都没有用multiset。
其它题解都是用权值线段树,或者是堆解决的问题。
但是权值线段树码量太大,堆跑得很慢。
为什么不了解一下~~又好写又跑得快~~的multiset呢?
```cpp
// P3573.CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
const int M = 1e6 + 5;
int n, m;
multiset<int> S;
struct edge {
int v, nxt;
} e[M << 1];
int head[2][N], cnt, in[N], q[N], l, r;
int dis[2][N];
inline void add(int u, int v, int t) {
e[++cnt].v = v;
e[cnt].nxt = head[t][u];
head[t][u] = cnt;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
in[v]++;
add(u, v, 0);
add(v, u, 1);
}
int pos = 0, dismin = n, tmp;
for (int i = 1; i <= n; i++)
if (in[i] == 0)
q[r++] = i;
while (l < r) {
int fr = q[l];
l++;
for (int i = head[0][fr]; i; i = e[i].nxt) {
int to = e[i].v;
in[to]--;
if (!in[to])
q[r++] = e[i].v;
}
}
for (int k = 0; k <= n - 1; k++)
for (int i = head[0][q[k]]; i; i = e[i].nxt)
dis[0][e[i].v] = max(dis[0][e[i].v], dis[0][q[k]] + 1);
for (int k = n - 1; k >= 0; k--)
for (int i = head[1][q[k]]; i; i = e[i].nxt)
dis[1][e[i].v] = max(dis[1][e[i].v], dis[1][q[k]] + 1);
for (int i = 1; i <= n; i++)
S.insert(dis[1][i]);
for (int k = 0; k <= n - 1; k++) {
S.erase(S.find(dis[1][q[k]]));
for (int i = head[1][q[k]]; i; i = e[i].nxt)
S.erase(S.find(dis[0][e[i].v] + dis[1][q[k]] + 1));
tmp = *S.rbegin();
if (tmp < dismin)
dismin = tmp, pos = q[k];
for (int i = head[0][q[k]]; i; i = e[i].nxt)
S.insert(dis[0][q[k]] + dis[1][e[i].v] + 1);
S.insert(dis[0][q[k]]);
}
cout << pos << " " << dismin << endl;
}
```