洛谷 P8724 [蓝桥杯 2020 省 AB3] 限高杆
洛谷题目传送门
题目描述
某市有 n 个路口，有 m 段道路连接这些路口，组成了该市的公路系统。其中一段道路两端一定连接两个不同的路口。道路中间不会穿过路口。
由于各种原因，在一部分道路的中间设置了一些限高杆，有限高杆的路段货车无法通过。
在该市有两个重要的市场 A 和 B，分别在路口 1 和 n 附近，货车从市场 A 出发，首先走到路口 1，然后经过公路系统走到路口 n，才能到达市场 B。两个市场非常繁华，每天有很多货车往返于两个市场之间。
市长发现，由于限高杆很多，导致货车可能需要绕行才能往返于市场之间，这使得货车在公路系统中的行驶路程变长，增加了对公路系统的损耗，增加了能源的消耗，同时还增加了环境污染。
市长决定要将两段道路中的限高杆拆除，使得市场 A 和市场 B 之间的路程变短。请问最多能减少多长的距离?
输入格式
输入的第一行包含两个整数 n，m，分别表示路口的数量和道路的段数。
接下来 mm 行，每行四个整数 a，b，c，d，表示路口 a 和路口 b 之间有一段长度为 c 的道路。如果 d 为 0，表示这段道路上没有限高杆; 如果 d 为 1，表示 这段道路上有限高杆。两个路口之间可能有多段道路。
输入数据保证在不拆除限高杆的情况下，货车能通过公路系统从路口 1 正常行驶到路口 n 。
输出格式
输出一行，包含一个整数，表示拆除两段道路的限高杆后，市场 A 和市场 B 之间的路程最大减少多长距离。
输入输出样例
输入
5 7 1 2 1 0 2 3 2 1 1 3 9 0 5 3 8 0 4 3 5 1 4 3 9 0 4 5 4 0
输出
6
说明/提示
【样例说明】
只有两段道路有限高杆，全部拆除后，1 到 n 的路程由原来的 17 变为了 11，减少了 6。
【评测用例规模与约定】
对于 30% 的评测样例，2≤n≤10,1≤m≤20,1≤c≤100。
对于 50% 的评测样例，2≤n≤100,1≤m≤1000,1≤c≤1000。
对于 70% 的评测样例，2≤n≤1000,1≤m≤10000,1≤c≤10000。
对于所有评测样例，2≤n≤10000,2≤m≤,1≤c≤10000，至少 有两段道路有限高杆。
蓝桥杯 2020 第三轮省赛 AB 组 H 题。
思路
由题目很明显看出是最短路
由于我们可以拆除 2 个 限高杆，由很多种情况，当最短路和选择在一起的时候，我们变要用分层思想
很明显看出，我们需要设计 0，1，2三层分别表示拆了0，1，2个限高杆的情况
如果两点之间有限高杆，那么我们就建立各个层之间的路径；否则就建立单层之间的路径
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=6e5+5;
ll n,m,w[N],di[N],dis[N],vis[N],to[N],ne[N],h[N],tot=0;
struct S{
ll x,y;
}a[N];
void add(ll u,ll v,ll d){
tot++;
to[tot]=v;
w[tot]=d;
ne[tot]=h[u];
h[u]=tot;
}
void spfa1(ll o){//求出不拆限高杆的情况下，货车到 n 的距离
memset(vis,0,sizeof(vis));
memset(di,0x7f,sizeof(di));
di[o]=0;vis[o]=1;queue<ll>q;q.push(o);
while(!q.empty()){
ll u=q.front();q.pop();vis[u]=0;
for(ll i=h[u];i;i=ne[i]){
ll v=to[i];
if(v>n)continue;//由于不拆限高杆，每次更新的点只能在第 0 层，即点的编号不大于 n
if(di[v]>di[u]+w[i]){
di[v]=di[u]+w[i];
if(!vis[v]){q.push(v);vis[v]=1;}
}
}
}
}
void spfa(ll o){//求出拆掉限高杆的情况下，货车到 n 的距离
memset(vis,0,sizeof(vis));
memset(dis,0x7f,sizeof(dis));
dis[o]=0;vis[o]=1;queue<ll>q;q.push(o);
while(!q.empty()){
ll u=q.front();q.pop();vis[u]=0;
for(ll i=h[u];i;i=ne[i]){
ll v=to[i];
if(dis[v]>dis[u]+w[i]){
dis[v]=dis[u]+w[i];
if(!vis[v]){q.push(v);vis[v]=1;}
}
}
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
int x,y,z,i1;
for(ll i=1;i<=m;i++){
cin>>x>>y>>z>>i1;
if(i1==0){add(x,y,z);add(y,x,z);add(x+n,y+n,z);add(y+n,x+n,z);add(x+n+n,y+n+n,z);add(y+n+n,x+n+n,z);}
//如果路上没有限高杆，则无论拆了几个限高杆，都可以走这条路，建立同层间的路
else{//否则建立跨越 0 层与 1 层 或 1 层与 2 层 的路，即向上跑一层
add(x,y+n,z);add(x+n,y+n+n,z);
add(y,x+n,z);add(y+n,x+n+n,z);
}
}
spfa1(1);
spfa(1);cout<<max(di[n]-dis[n],max(di[n]-dis[n+n],di[n]-dis[n+n+n]));//最大的变化量可能在 n , 2n , 3n 上取到
return 0;
}