\(4 \le n \le 3000\)
说明可以用 \(n^2\) 的做法，题目要求 \(4\) 个点的最短路最长，共 \(3\) 条路经，则枚举 \(2\) 个点。
如果枚举 \(a, c\)，则要找 \(b, d\)，但 \(b\) 和 \(c\) 也要判断路径，比较麻烦，所以直接枚举 \(b, c\)。
然后枚举 \(b, c\) 对应的最短路最长的点，因为枚举点共会 \(6\) 种重合情况，而 \(b, c\) 已经判掉了，所以只有 \(5\) 种情况，就直接枚举最短路最长的前 \(5\) 个 \(a\)，\(d\) 同理。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
#define d first
#define id second
using namespace std;
constexpr int N = 3e3 + 5;
int n, m, vis[N];
vector<int> g[N];
int pre[N][N], dx[N][N];
pair<int, int> dis[N][N];
inline void dij(int s) {
memset(dis[s], -1, sizeof(dis[s]));
dis[s][s].d = 0;
memset(dx[s], -1, sizeof(dx[s]));
dx[s][s] = 0;
for (int i = 1; i <= n; ++i)
dis[s][i].id = i;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, s});
while (!q.empty()) {
int u = q.top().id;
q.pop();
vis[u] = 1;
for (int l = 0; l < g[u].size(); ++l) {
int i = g[u][l];
if (dis[s][i].d > dis[s][u].d + 1 || dis[s][i].d == -1) {
dis[s][i].d = dis[s][u].d + 1;
dx[s][i] = dx[s][u] + 1;
if (!vis[i]) q.push({dis[s][i].d, i});
}
}
}
sort(dis[s] + 1, dis[s] + n + 1, greater<pair<int, int>>());
}
int id;
inline bool cmp(int a, int b) {
return dx[a][id] > dx[b][id];
}
inline void special() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
if (dx[j][i] != -1) pre[i][j] = j;
id = i;
sort(pre[i] + 1, pre[i] + n + 1, cmp);
}
}
signed main() {
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
}
for (int i = 1; i <= n; ++i) {
memset(vis, 0, sizeof(vis));
dij(i);
// cerr << "DIJ " << i << '\n';
// for (int j = 1; j <= n; ++j)
// cerr << " " << dis[i][j].id << ' ' << dis[i][j].d << '\n';
}
special();
int ans = 0, anss[5];
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k) {
if (j == k || dx[j][k] == -1) continue;
for (int ix = 1; ix <= min(3, n); ++ix) {
int i = pre[j][ix];
if (i == j || k == i || i == 0) continue;
for (int lx = 1; lx <= min(3, n); ++lx) {
int l = dis[k][lx].id;
if (i == l || k == l || j == l || l == 0) continue;
if (ans < dx[i][j] + dx[j][k] + dx[k][l]) {
ans = dx[i][j] + dx[j][k] + dx[k][l];
// printf("YEAH %d %d %d %d\n %d %d %d\n", i, j, k, l, dx[i][j], dx[j][k], dx[k][l]);
anss[1] = i, anss[2] = j, anss[3] = k, anss[4] = l;
}
}
}
}
for (int i = 1; i <= 4; ++i)
cout << anss[i] << ' ';
return 0;
}