题目链接：http://codeforces.com/problemset/problem/666/B
大意是给一张有向图，选取四个点，使得走这四个点，任意两个点之间走最短路，总距离最长。
3000个点直接floyd肯定不行，但是注意到任意每条路距离都是1，其实可以枚举所有源点作bfs，求出距离数组。
然后对于每个点求出以这个点为入点和出点距离最大的3个点。再根据这个信息，枚举四个点中的中间两个，再枚举这两个点距离他们最远的那3*3种情况，判断是否有重复，没有重复的话，更新答案。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std; const int N=; vector<int>edge[N];
int dis[N][N];
int n;
void bfs(int s) {
queue< pair<int,int> >que;
que.push(make_pair(s,));
dis[s][s]=;
while (!que.empty()) {
pair<int,int> now=que.front();
que.pop();
int u=now.first,d=now.second;
for (int i=;i<edge[u].size();i++) {
int v=edge[u][i];
if (dis[s][v]>=) continue;
dis[s][v]=d+;
que.push(make_pair(v,d+));
}
}
}
pair<int,int> in[N][],out[N][];
void upd(pair<int,int> x,pair<int,int> *y) {
for (int i=;i<;i++) {
if (x>y[i]) {
for (int j=;j>i;j--) {
y[j]=y[j-];
}
y[i]=x;
break;
}
}
}
void solve() {
memset(dis,-,sizeof dis);
for (int i=;i<=n;i++){
bfs(i);
for (int j=;j<;j++) {
in[i][j]=make_pair(-,-);
out[i][j]=make_pair(-,-);
}
}
for (int i=;i<=n;i++) {
for (int j=;j<=n;j++) {
if (i==j) continue;
if (dis[i][j]==-) continue;
upd(make_pair(dis[i][j],i),in[j]);
upd(make_pair(dis[i][j],j),out[i]);
}
}
int best=;
int a=-,b=-,c=-,d=-;
for (int i=;i<=n;i++) {
for (int j=;j<=n;j++) {
if (i==j) continue;
if (dis[i][j]==-) continue;
for (int p=;p<;p++) {
if (in[i][p].first==-) continue;
int ii=in[i][p].second;
if (ii==j) continue;
for (int q=;q<;q++) {
if (out[j][q].first==-) continue;
int jj=out[j][q].second;
if (jj==i||jj==ii) continue; int tot=dis[ii][i]+dis[i][j]+dis[j][jj];
if (tot>best) {
best=tot;
a=ii;b=i;c=j;d=jj;
}
}
}
}
}
printf("%d %d %d %d\n",a,b,c,d);
}
int main () {
int m;
scanf("%d %d",&n,&m);
for (int i=;i<=m;i++) {
int u,v;
scanf("%d %d",&u,&v);
edge[u].push_back(v);
}
solve();
return ;
}