大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说P2865 [USACO06NOV]Roadblocks G/【模板】次短路,希望您对编程的造诣更进一步.
![P2865 [USACO06NOV]Roadblocks G/【模板】次短路[数据库教程]](https://www.yht7.com/upload/image/images/imgsql/15.jpg "P2865 [USACO06NOV]Roadblocks G/【模板】次短路插图")
![P2865 [USACO06NOV]Roadblocks G/【模板】次短路[数据库教程]](/wp-content/themes/justnews/themer/assets/images/lazy.png "P2865 [USACO06NOV]Roadblocks G/【模板】次短路插图1")
不是可持久化可并堆的事么
在spfa/dij的不等式中间加一个判断，看他能不能更新最短路/次短路。
这题不卡spfa是！！！
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
vector<pair<int,int> > e[maxn];
int n,m;
int dis[maxn][2];
bool vis[maxn];
void spfa(int s){
memset(dis,0x3f3f3f3f,sizeof(dis));
dis[s][0]=0,vis[s]=1;
queue<int> q;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
for(auto E:e[u]){
int v=E.first,w=E.second;
if(dis[v][0]>dis[u][0]+w){//最短路更新
dis[v][1]=dis[v][0];
dis[v][0]=dis[u][0]+w;
if(!vis[v])vis[v]=1,q.push(v);
}
if(dis[v][1]>dis[u][0]+w&&dis[v][0]<dis[u][0]+w){//次短路更新
dis[v][1]=dis[u][0]+w;
if(!vis[v])vis[v]=1,q.push(v);
}
if(dis[v][1]>dis[u][1]+w){//必然不能更新最短路，因为若能更新，已经被该节点最短路更新力
dis[v][1]=dis[u][1]+w;
if(!vis[v])vis[v]=1,q.push(v);
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
e[x].push_back(make_pair(y,w));
e[y].push_back(make_pair(x,w));
}
spfa(1);
cout<<dis[n][1];
return 0;
}
P2865 [USACO06NOV]Roadblocks G/【模板】次短路
原文：https://www.cnblogs.com/kkksc0100/p/spfa-is-undead.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/5952.html
