网站开发访客ip,网站开发就业前景分析,wordpress调整文章编辑界面,推客平台有哪些正题
题目链接:https://www.luogu.com.cn/problem/P2149 题目大意 nnn个点mmm条边的一张无向图#xff0c;给定两个起点和对应的终点。求两个最短路的最长公共距离 解题思路
首先要求是最短路#xff0c;我们可以先跑一次第一个起点的SPFASPFASPFA#xff0c;然后从终点开…正题
题目链接:https://www.luogu.com.cn/problem/P2149 题目大意
nnn个点mmm条边的一张无向图给定两个起点和对应的终点。求两个最短路的最长公共距离 解题思路
首先要求是最短路我们可以先跑一次第一个起点的SPFASPFASPFA然后从终点开始dfsdfsdfs保留所有的最短路。
这样我们可以保证剩下的图中的边一定是最短路上的边之后考虑如何求答案。
我们可以再从第二个起点开始再跑一次单源最短路保留数组之后对于一条边如果即是第一个最短路的又是第二个最短路上的话我们就可以用类似于SPFASPFASPFA的方法来更新答案
时间复杂度O(n2)O(n^2)O(n2)(SPFA通通n2n^2n2处置) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N1600;
struct node{int to,next,w;bool flag;
}a[N*N];
int n,m,tot1,ans;
int s1,s2,t1,t2;
int ls[N],f[N],g[N];
bool v[N],vis[N];
queueint q;
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void SPFA(int s){memset(f,0x3f,sizeof(f));memset(v,0,sizeof(v));q.push(s);v[s]1;f[s]0;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;if(!v[y]){v[y]1;q.push(y);}}}v[x]0;}return;
}
void dfs(int x){v[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(f[y]a[i].wf[x]){a[i].flaga[i^1].flag1;if(!v[y])dfs(y);}}return;
}
void get_ans(){q.push(t2);v[t2]vis[t2]1;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(f[y]a[i].wf[x]){if(a[i].flagg[x]a[i].wg[y]){g[y]max(g[y],g[x]a[i].w);ansmax(ans,g[y]);if(!v[y]){v[y]1;q.push(y);}}if(!vis[y]){vis[y]v[y]1;q.push(y);}}}v[x]0;}return;
}
int main()
{scanf(%d%d,n,m);scanf(%d%d%d%d,s1,t1,s2,t2);for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}SPFA(s1);dfs(t1);SPFA(s2);get_ans();printf(%d,ans);
}
