题解：P10206 [JOI 2024 Final] 建设工程 2 / Construction Project 2

· · 题解

题意

给定一个无向图，可以在任意两点间建一条长度为 L 的边，求建边后 S 到 T 的最短路长度 \le K 的方案数。

思路

观察如下图示(有点丑)。

不妨设点 S 到点 w 的最短路长度为 dis1_w ，点 T 到点 w 的最短路长度为 dis2_w 。在如上情况中，添加一条连接 u 与 v 的长度为 L 的边后， dis1_T （即 S 到 T 的最短路长度）为 \min\{dis1_u+L+dis2_v,dis1_T\} 我们的目的就转换为求 dis1_u+L+dis2_v \le K 的个数。

进一步转换，将原式移项得： K - L - dis2_v \le dis1_u 。

跑两次最短路可分别求出 dis1 和 dis2 每一项的值，最终答案可使用二分求解。

代码

#include<bits/stdc++.h>
#define int long long
#define double long double
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
int n,m;
int s,t,l,k;
struct node{
    int v,w;
};
vector<node>g[N];
int dis1[N],dis2[N];
bool vis1[N],vis2[N];
struct node2{
    int u,dis;
    bool operator>(const node2 &a)const{
        return dis>a.dis;
    }
};
priority_queue<node2,vector<node2>,greater<node2> >pq1,pq2;
void dij1(){//求dis1
    memset(dis1,0x3f,sizeof dis1);
    dis1[s]=0;
    pq1.push({s,0});
    while(pq1.size()){
        int u=pq1.top().u;
        pq1.pop();
        if(vis1[u]){
            continue;
        }
        vis1[u]=1;
        for(auto i:g[u]){
            int v=i.v,w=i.w;
            if(dis1[v]>dis1[u]+w){
                dis1[v]=dis1[u]+w;
                pq1.push({v,dis1[v]});
            }
        }
    }
    return ;
}
void dij2(){//求dis2
    memset(dis2,0x3f,sizeof dis2);
    dis2[t]=0;
    pq2.push({t,0});
    while(pq2.size()){
        int u=pq2.top().u;
        pq2.pop();
        if(vis2[u]){
            continue;
        }
        vis2[u]=1;
        for(auto i:g[u]){
            int v=i.v,w=i.w;
            if(dis2[v]>dis2[u]+w){
                dis2[v]=dis2[u]+w;
                pq2.push({v,dis2[v]});
            }
        }
    }
    return ;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    cin>>s>>t>>l>>k;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    dij1();
    dij2();
    if(dis1[t]<=k){
        cout<<n*(n-1)/2<<endl;
        return 0;
    }
    sort(dis1+1,dis1+1+n);
    int ans=0;
    for(int v=1;v<=n;v++){
        int tmp=k-l-dis2[v];//转换后的式子
        int lb=upper_bound(dis1+1,dis1+1+n,tmp)-dis1-1;//二分求答案
        ans+=lb;
    }
    cout<<ans<<endl;
    return 0;
}