洛谷P2349 金字塔题解

洛谷P2349 金字塔题解

题目传送门 – Luogu （最近好像又拖更了……）

废话

我的精神状态： 今天更新没有？ 好像更了，又好像没更，明天再说吧

题目大意

有一个无向图，从

1

1

1 节点开始，跑到第

n

n

n 节点，现在触发了烟雾，会让图中一条边的边权翻倍，找出最坏情况下的最短路

思路

考虑使用美丽迷人的

S

P

F

A

SPFA

SPFA 算法，

n

≤

100

,

m

≤

1000

n\\le 100 , m \\le1 000

n≤100,m≤1000 的数据量应该不会爆

我们可以爆改一下

S

P

F

A

SPFA

SPFA 的松弛条件，在

d

i

s

u

+

w

+

max

⁡

{

m

e

u

,

w

}

<

d

i

s

v

+

m

e

v

dis_u+w+\\max\\{me_u,w\\}<dis_v+me_v

disu​+w+max{meu​,w}<disv​+mev​ 时进行松弛，同时维护最短路数组

m

e

me

me ：

m

e

v

=

m

a

x

{

m

e

u

,

w

}

me_v=max\\{me_u,w\\}

mev​=max{meu​,w}

最后输出

d

i

s

n

+

m

e

n

dis_n+me_n

disn​+men​

实现

首先对

v

i

s

vis

vis （用于优化），

d

i

s

dis

dis ，

m

e

me

me 三个数组初始化：

memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
memset(me,63,sizeof me);

然后跑 SPFA ，注意修改松弛条件：

while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(auto it:e[u]){
int v=it.first,w=it.second;
if(dis[u]+w+max(me[u],w)<dis[v]+me[v]){
dis[v]=dis[u]+w;
me[v]=max(me[u],w);
if(!vis[v])q.push(v),vis[v]=1;
}
}
}

记得建图时建无向图

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int,int>>e[110];
int vis[110],dis[110],me[110];
void solve(int s){
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
memset(me,63,sizeof me);
queue<int>q;
q.push(s);
dis[s]=0;
vis[s]=1;
me[s]=0;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(auto it:e[u]){
int v=it.first,w=it.second;
if(dis[u]+w+max(me[u],w)<dis[v]+me[v]){
dis[v]=dis[u]+w;
me[v]=max(me[u],w);
if(!vis[v])q.push(v),vis[v]=1;
}
}
}
}
signed main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
solve(1);
cout<<dis[n]+me[n];
return 0;
}

AC记录

大家再见，记得👍+❤️