G7020 [GESP202603 七级] 物流网络 题解

知识点：最短路、离线排序、枚举边权阈值。

解题思路

按景观评分分组升序加边，当前阈值图只含评分不超过B的边。跑从1和n出发的Dijkstra，对本组每条可免费边(u,v)评估dist1[u]+distn[v]及反向组合。

为什么正确

任一优惠路线都有一条最高评分免费边，其他边均在对应阈值图；去掉该边的费用由两端最短距离下界给出，枚举全部评分与免费边可达到最优。

易错点

同评分边必须整组加入后再求最短路；免费边自身w不计入，两种方向都需评估，n=1为0。

复杂度

时间O(m(n+m)log n)保守上界，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    struct E {
        int u,v;
        long long w,b;
    }
    ;
    vector<E>e(m);
    for(auto &x:e)cin>>x.u>>x.v>>x.w>>x.b;
    sort(e.begin(),e.end(),[](auto a,auto b){return a.b<b.b;});
    vector<vector<pair<int,long long>>>g(n+1);
    long long ans=(1LL<<60);
    auto dij=[&](int s) {
        vector<long long>d(n+1,1LL<<60);
        priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
        d[s]=0;
        q.push({0,s});
        while(!q.empty()) {
            auto [dist,u]=q.top();
            q.pop();
            if(dist!=d[u])continue;
            for(auto [v,w]:g[u])if(d[v]>dist+w) {
                d[v]=dist+w;
                q.push({d[v],v});
            }
        }
        return d;
    }
    ;
    if(n==1)ans=0;
    for(int l=0;l<m;) {
        int r=l;
        while(r<m&&e[r].b==e[l].b) {
            g[e[r].u].push_back({e[r].v,e[r].w});
            g[e[r].v].push_back({e[r].u,e[r].w});
            r++;
        }
        auto d1=dij(1),dn=dij(n);
        for(int j=l;j<r;j++) {
            auto x=e[j];
            ans=min({ans,d1[x.u]+dn[x.v],d1[x.v]+dn[x.u]});
        }
        l=r;
    }
    cout<<(ans==(1LL<<60)?-1:ans);
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用18个自行生成的测试点。