只需要在最短路的基础上改亿改就可以了
两个数组
(dis1[])存储最短路
(dis2[])存储次短路
次短路分三种情况
- 可以更新最短路，次短路继承更新前的最短路，然后更新最短路（原因很简单，因为目前的最短路可以更新说明这不是最短路，但可能是此次短路
- 不能更新最短路，但可以更新次短路，但更新次短路的条件一定满足不小于最短路
- 都不能更新（废话
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int n,m,cnt=0;
int head[maxn<<1]; struct node{ int v,next,w; }e[maxn<<1]; void add(int u,int v,int w){ 链式前向星 e[++cnt].v="v;" e[cnt].w="w;" e[cnt].next="head[u];" head[u]="cnt;" } dis1[maxn]; dis2[maxn]; dj(){ memset(dis1,0x3f,sizeof(dis1)); 初始化 memset(dis2,0x3f,sizeof(dis2)); dis1[1]="0;" priority_queue<pair<int,int> >q;
q.push(make_pair(-dis1[1],1));
while(!q.empty()){
int u=q.top().second,dis=-q.top().first;
q.pop();
for(int i=head[u];i;i=e[i].next){
int v=e[i].v,w=e[i].w;
if(dis1[v]>dis+w){//更新最短路
dis2[v]=dis1[v];//更新次短路
dis1[v]=dis+w;//更新最短路
q.push(make_pair(-dis1[v],v));
}
if(dis2[v]>dis+w && dis+w>dis1[v]){//更新最短路
dis2[v]=dis+w;
q.push(make_pair(-dis2[v],v));
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){ int u,v,w; cin>>u>>v>>w;
add(u,v,w);add(v,u,w);
}
dj();
cout<<dis2[n]<<endl; return 0; } < code></dis2[n]<<endl;></=m;++i){></1];></algorithm></queue></iostream></cstring></cstdio>
ZFY AK IOI
Original: https://www.cnblogs.com/guiyou/p/15171840.html
Author: 归游
Title: [USACO06NOV]Roadblocks G /次短路模板
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584606/
转载文章受原作者版权保护。转载请注明原作者出处！