传送门：点击打开链接
题意：有向边n个点，m条边(n < 3000, m < 4000)，现在选出不相同的4个点，要求a->b->c->d的路径最大，从u->v走的路径必须是最短路。
题目保证存在4个点可以走到。
思路：先BFS预处理出所有的从u到v的最短路径，并保存其他点到u的最短路径和次短路径，并保存好方案
保存u到其他点的最短路径和次短路径，并保存好方案
之后枚举b和c，通过之前保存的最短路和次短路组合起来，取最大值，就搞定了
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 3e3 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;struct Edge {int v, nxt;
} E[20000];
int Head[MX], rear;
void edge_init() {rear = 0;memset(Head, -1, sizeof(Head));
}
void edge_add(int u, int v) {E[rear].v = v;E[rear].nxt = Head[u];Head[u] = rear++;
}int n, m, d[MX], G[MX][MX];
int to[2][MX], from[2][MX];
int toid[2][MX], fromid[2][MX];bool check(int a, int b, int c, int d) {int s[] = {a, b, c, d};sort(s, s + 4);int sz = unique(s, s + 4) - s;return sz == 4;
}
int main() {edge_init(); //FIN;scanf("%d%d", &n, &m);for(int i = 1; i <= m; i++) {int u, v;scanf("%d%d", &u, &v);edge_add(u, v);}for(int i = 1; i <= n; i++) {memset(d, INF, sizeof(d));queue<int> Q;d[i] = 0; Q.push(i);while(!Q.empty()) {int u = Q.front(); Q.pop();for(int j = Head[u]; ~j; j = E[j].nxt) {int v = E[j].v;if(d[v] == INF) {d[v] = d[u] + 1;Q.push(v);}}}for(int j = 1; j <= n; j++) {if(d[j] != INF) {G[i][j] = d[j];if(from[0][j] < d[j]) {from[1][j] = from[0][j]; fromid[1][j] = fromid[0][j];from[0][j] = d[j]; fromid[0][j] = i;} else if(from[1][j] < d[j]) {from[1][j] = d[j]; fromid[1][j] = i;}if(to[0][i] < d[j]) {to[1][i] = to[0][i]; toid[1][i] = toid[0][i];to[0][i] = d[j]; toid[0][i] = j;} else if(to[1][i] < d[j]) {to[1][i] = d[j]; toid[1][i] = j;}}}}int a, b, c, d, Max = 0;for(int u = 1; u <= n; u++) {for(int v = 1; v <= n; v++) {for(int i = 0; i <= 1; i++) {for(int j = 0; j <= 1; j++) {if(G[u][v] && from[i][u] && to[j][v]) {if(check(u, v, fromid[i][u], toid[j][v]) && Max < G[u][v] + from[i][u] + to[j][v]) {Max = G[u][v] + from[i][u] + to[j][v];a = fromid[i][u]; b = u; c = v; d = toid[j][v];}}}}}}printf("%d %d %d %d\n", a, b, c, d);return 0;
}