当前位置：首页 > news >正文

P2865 [USACO06NOV] Roadblocks G

news 2025/4/24 18:59:40

*原题链接*

次短路模版题

在刚学最短路时，我做过这道题集合位置，那时博客上写的是枚举删除最短路上的边，然后求解。不过这种做法最坏时间复杂度可以有 $O(m^2logn)$ ，对于这道题数据范围较大，所以可以用更好写，思维难度也不高的方法来解决。

首先记录 $dist_{i,0/1}$ 数组，分别表示到 $i$ 的最短路，次短路。设此时用 $t$ 更新 $y$ ，则我们分别考虑如何更新最短路和次短路，在就是本题求的是严格次短路，注意判断条件。具体见代码注释。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}int n,m,head[N],tot,dist[N][2],vis[N];struct node{int to,nxt,w;
}edge[N*2];
void add(int x,int y,int w){edge[++tot].to=y;edge[tot].w=w;edge[tot].nxt=head[x];head[x]=tot;
}void spfa(int s){queue<int> q;memset(dist,0x3f,sizeof(dist)),memset(vis,0,sizeof(vis));q.push(s),dist[s][0]=0,vis[s]=1;while(!q.empty()){int t=q.front();q.pop();vis[t]=0;for(int i=head[t];i;i=edge[i].nxt){int y=edge[i].to;if(dist[y][0]>dist[t][0]+edge[i].w){//可以更新最短路dist[y][1]=dist[y][0];别忘了先更新y的次短路dist[y][0]=dist[t][0]+edge[i].w;if(!vis[y]) vis[y]=1,q.push(y);}//不能更新y的最短路，但可以用t的最短路更新y的次短路if(dist[y][1]>dist[t][0]+edge[i].w&&dist[t][0]+edge[i].w>dist[y][0]){dist[y][1]=dist[t][0]+edge[i].w;if(!vis[y]) vis[y]=1,q.push(y);//这时也要入队}//用t的次短路更新y的次短路if(dist[y][1]>dist[t][1]+edge[i].w){dist[y][1]=dist[t][1]+edge[i].w;if(!vis[y]) vis[y]=1,q.push(y);}}}
}int main(){n=read(),m=read();for(int i=1;i<=m;i++){int x=read(),y=read(),w=read();add(x,y,w),add(y,x,w);}spfa(n);cout<<dist[1][1]<<endl;return 0;
}

查看全文

http://www.mrgr.cn/news/26926.html