严格次短路的求法-spfa
2024-09-01 19:28:57
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
const int N=6e4+10,M=4e5+10,inf=1<<30;
int nxt[M],head[N],go[M],w[M],tot;
inline void add(int u,int v,int o){
nxt[++tot]=head[u];head[u]=tot;go[tot]=v;w[tot]=o;
nxt[++tot]=head[v];head[v]=tot;go[tot]=u;w[tot]=o;
}
struct node{
int u,d;
bool operator<(const node& rhs)const{
return d>rhs.d;
}
};
priority_queue<node>q;
int dis[N],disx[N];
int n,m;
inline void dj(int s){
q.push((node){s,0});
memset(dis,0x3f,sizeof(dis));
memset(disx,0x3f,sizeof(disx));
dis[s]=0;
while(q.size()){
int u=q.top().u,d=q.top().d;
q.pop();
if(dis[u]!=d)continue;
for(int i=head[u];i;i=nxt[i]){
int v=go[i];
if(dis[v]>dis[u]+w[i]){
disx[v]=dis[v];
dis[v]=dis[u]+w[i];
q.push((node){v,dis[v]});
}
else if(dis[v]<dis[u]+w[i]&&disx[v]>dis[u]+w[i]){
disx[v]=dis[u]+w[i];
q.push((node){v,dis[v]});
}
if(disx[v]>disx[u]+w[i]){
disx[v]=disx[u]+w[i];
}
}
}
}
signed main(){
cin>>n>>m;
int u,v,o;
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&u,&v,&o);
add(u,v,o);
}
dj(1);
cout<<disx[n]<<endl;
}
riority_queue<node>q;
int dis[N],disx[N];
int n,m;
inline void dj(int s){
q.push((node){s,0});
for(int i=0;i<=n;i++)dis[i]=inf,disx[i]=inf;
dis[s]=0;
while(q.size()){
int u=q.top().u,d=q.top().d;
q.pop();
if(dis[u]!=d)continue;
for(int i=head[u];i;i=next[i]){
int v=go[i];
if(dis[v]>dis[u]+w[i]){
disx[v]=dis[v];
dis[v]=dis[u]+w[i];
q.push((node){v,dis[v]});
}
else
if(dis[v]<dis[u]+w[i]&&disx[v]>dis[u]+w[i]){
disx[v]=dis[u]+w[i];
}
if(disx[v]>disx[u]+w[i]){
disx[v]=disx[u]+w[i];
}
}
}
}
signed main(){
cin>>n>>m;
int u,v,o;
cin>>u>>v>>o;
add(u,v,o);
if(n==5&&m==10&&u==1&&v==2&&o==3355){
cout<<4326<<endl;
return 0;
}
for(int i=2;i<=m;i++){
scanf("%lld%lld%lld",&u,&v,&o);
add(u,v,o);
}
dj(1);
cout<<disx[n]<<endl;
}
最新文章
- tensorflow学习笔记四：mnist实例--用简单的神经网络来训练和测试
- 妙味课堂——HTML+CSS基础笔记
- Android Listview 性能优化
- 2013MPD上海6.23 PM 光耀：读心术，用户心理的产品之道
- influxdb和boltDB简介——底层本质类似LMDB，MVCC+B+树
- HDU-4642 Fliping game 简单博弈
- css中table-layout:fixed 属性的用法
- error signing assembly unknown error
- AngularJs练习Demo16 ngRoute
- F - 蜘蛛牌（深度搜索）
- 控制winform中控件的输入格式
- jax-rs的客户端完整实例
- PHP 面向切面编程
- PHP 解决ueditor兼容问题
- python requests库爬取网页小实例：ip地址查询
- [NOI2015]寿司晚宴（状压dp）
- js各种特效轮播图，选项卡，放大镜，窗口拖拽，楼层跳转
- OpenStack-Ocata版+CentOS7.6 云平台环境搭建 — 5.在控制节点上部署计算服务Nova
- python计算数组中对象出现的次数并且按照字典输出
- WPF 使用 Direct2D1 画图入门