题目大意：
题目链接：https://jzoj.net/senior/#main/show/4671
Cicasso是一个著名的雕塑家。
现在他想去城市之间旅游，他是一个聪明的人，所以从一个城市到另一个城市他只会走最短路。他想游览全国的风景，所以他想走的路的总长度尽量长，但是经费有限，他只能去四个城市，而且这四个城市不能重复（在途中经过的城市不计算，例如 ，他要去的四个城市有用红色标注，[1, 5, 2, 4]，这样是合法的）
注意，道路是单向路，并且距离都为1。
思路:
这是A组题？？？
虽然我考试时没有做出来
先用堆优化求出所有点之间的最短路（似乎也没有卡），然后求出距离每一个点最远、次远的点。
最后枚举两个点和，把看成是答案中的一条边，用它们和最远、次远的点去更新答案即可。
时间复杂度
代码：
//以下代码巨丑，请见谅QWQ
#include <queue>
#include <cstdio>
#include <iostream>
#include <cstring>
#define mp make_pair
using namespace std;
const int N=3010;
const int M=5010;
const int Inf=1e9;
int n,m,x,y,tot,ans,a,b,c,d;
int head[N],dis[N][N],maxn[N][3][3],maxx[N][3][3];
bool vis[N];
struct edge
{
int next,to;
}e[M];
void add(int from,int to)
{
e[++tot].to=to;
e[tot].next=head[from];
head[from]=tot;
}
void dij(int S) //求最短路
{
memset(vis,0,sizeof(vis));
priority_queue<pair<int,int> > q;
q.push(mp(0,S));
dis[S][S]=0;
vis[S]=1;
while (q.size())
{
int u=q.top().second;
q.pop();
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (dis[S][v]>dis[S][u]+1)
{
dis[S][v]=dis[S][u]+1;
if (!vis[v])
{
q.push(mp(-dis[S][v],v));
vis[v]=1;
}
}
}
}
}
bool check(int x1,int x2,int x3,int x4) //判断四个数字是否互不相同
{
if (x1==x2) return 0;
if (x1==x3) return 0;
if (x1==x4) return 0;
if (x2==x3) return 0;
if (x2==x4) return 0;
if (x3==x4) return 0;
return 1;
}
int main()
{
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
for (int i=1;i<=n;i++)
dij(i);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (dis[i][j]<Inf)
{
if (dis[i][j]>maxn[i][1][1]) //预处理出最长、次长路径
{
maxn[i][1][2]=maxn[i][1][1];
maxx[i][1][2]=maxx[i][1][1];
maxn[i][1][1]=dis[i][j];
maxx[i][1][1]=j;
}
else if (dis[i][j]>maxn[i][1][2])
{
maxn[i][1][2]=dis[i][j];
maxx[i][1][2]=j;
}
if (dis[i][j]>maxn[j][2][1])
{
maxn[j][2][2]=maxn[j][2][1];
maxx[j][2][2]=maxx[j][2][1];
maxn[j][2][1]=dis[i][j];
maxx[j][2][1]=i;
}
else if (dis[i][j]>maxn[i][2][2])
{
maxn[j][2][2]=dis[i][j];
maxx[j][2][2]=i;
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
if (i==j) continue;
if (dis[i][j]<Inf&&dis[i][j]+maxn[i][2][1]+maxn[j][1][1]>ans&&check(maxx[i][2][1],maxx[j][1][1],i,j))
{
ans=dis[i][j]+maxn[i][2][1]+maxn[j][1][1];
d=maxx[j][1][1]; c=j;
b=i; a=maxx[i][2][1];
}
if (dis[i][j]<Inf&&dis[i][j]+maxn[i][2][2]+maxn[j][1][1]>ans&&check(maxx[i][2][2],maxx[j][1][1],i,j))
{
ans=dis[i][j]+maxn[i][2][2]+maxn[j][1][1];
d=maxx[j][1][1]; c=j;
b=i; a=maxx[i][2][2];
}
if (dis[i][j]<Inf&&dis[i][j]+maxn[i][2][1]+maxn[j][1][2]>ans&&check(maxx[i][2][1],maxx[j][1][2],i,j))
{
ans=dis[i][j]+maxn[i][2][1]+maxn[j][1][2];
d=maxx[j][1][2]; c=j;
b=i; a=maxx[i][2][1];
}
}
printf("%d %d %d %d",a,b,c,d);
return 0;
}