正題

題目鏈接:https://www.luogu.com.cn/problem/P2149

---

題目大意

$n$個(gè)點(diǎn)$m$條邊的一張無向圖，給定兩個(gè)起點(diǎn)和對(duì)應(yīng)的終點(diǎn)。求兩個(gè)最短路的最長公共距離

---

解題思路

首先要求是最短路，我們可以先跑一次第一個(gè)起點(diǎn)的$SPFA$，然后從終點(diǎn)開始$dfs$保留所有的最短路。

這樣我們可以保證剩下的圖中的邊一定是最短路上的邊，之后考慮如何求答案。

我們可以再從第二個(gè)起點(diǎn)開始再跑一次單源最短路，保留數(shù)組，之后對(duì)于一條邊如果即是第一個(gè)最短路的又是第二個(gè)最短路上的話我們就可以用類似于$SPFA$的方法來更新答案

時(shí)間復(fù)雜度$O(n^2)$(SPFA通通$n^2$處置)

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1600; struct node{int to,next,w;bool flag; }a[N*N]; int n,m,tot=1,ans; int s1,s2,t1,t2; int ls[N],f[N],g[N]; bool v[N],vis[N]; queue<int> q; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;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 x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[x]+a[i].w<f[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 i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[y]+a[i].w==f[x]){a[i].flag=a[i^1].flag=1;if(!v[y])dfs(y);}}return; } void get_ans(){q.push(t2);v[t2]=vis[t2]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[y]+a[i].w==f[x]){if(a[i].flag&&g[x]+a[i].w>g[y]){g[y]=max(g[y],g[x]+a[i].w);ans=max(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 i=1;i<=m;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); }

總結(jié)

以上是生活随笔為你收集整理的P2149-[SDOI2009]Elaxia的路线【最短路】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。