网站设计费用一览表,做外汇的官方网站,鄂州网站设计制作公司,asp网站背景正题
luogu题目链接:https://www.luogu.org/problemnew/show/CF666B 题目大意
求4个点#xff0c;使得这4个点按顺序最短路到达的长度最远。 解题思路
用bfsbfsbfs求出每个点之间的最短路#xff0c;然后对于每个点求出最远点#xff0c;次远点#xff0c;反最远点和反次…正题
luogu题目链接:https://www.luogu.org/problemnew/show/CF666B 题目大意
求4个点使得这4个点按顺序最短路到达的长度最远。 解题思路
用bfsbfsbfs求出每个点之间的最短路然后对于每个点求出最远点次远点反最远点和反次远点。 之后枚举中间两个点然后如果最远的相同就一个用次远否则都用最远。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N5100,M10100;
struct edge{int to,next;
}a[M];
int n,tot,m,f[N][N],maxs,ls[N],mark[4];
int ffar[N],ffar2[N],far[N],far2[N];
queueint q;
void adde(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void bfs(int s)
{q.push(s);f[s][s]0;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(f[s][y]0){f[s][y]f[s][x]1;q.push(y);}}}
}
int main()
{memset(f,0xcf,sizeof(f));scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);adde(x,y);}for(int i1;in;i)bfs(i);for(int i1;in;i){for(int j1;jn;j){if(ij) continue;if(f[i][j]f[i][far[i]]){far2[i]far[i];far[i]j;}else if(f[i][j]f[i][far2[i]])far2[i]j;}}for(int i1;in;i){for(int j1;jn;j){if(ij) continue;if(f[j][i]f[ffar[i]][i]){ffar2[i]ffar[i];ffar[i]j;}else if(f[j][i]f[ffar2[i]][i])ffar2[i]j;}}for(int i1;in;i)for(int j1;jn;j)if(i!j){if(!ffar[i]||!far[j]||ffar[i]j||far[j]i) continue;if(ffar[i]far[j]){if(f[ffar2[i]][i]f[j][far[j]]f[i][j]maxsffar2[i]){maxsf[ffar2[i]][i]f[j][far[j]]f[i][j];mark[0]ffar2[i];mark[1]i;mark[2]j;mark[3]far[j];}if(f[ffar[i]][i]f[j][far2[j]]f[i][j]maxsfar2[j]){maxsf[ffar[i]][i]f[j][far2[j]]f[i][j];mark[0]ffar[i];mark[1]i;mark[2]j;mark[3]far2[j];}}elseif(f[ffar[i]][i]f[j][far[j]]f[i][j]maxs){maxsf[ffar[i]][i]f[j][far[j]]f[i][j];mark[0]ffar[i];mark[1]i;mark[2]j;mark[3]far[j];}}printf(%d %d %d %d,mark[0],mark[1],mark[2],mark[3]);
}
