P15803 [GESP202603 七级] 物流网络

Nostopathy · 2026-03-16 19:56:02 · 题解

枚举免费边，在跑最短路时，如果遇到该公路边权计为 0。这条免费边的边权需要不小于其它所有边权才有保证，故按照参数 b 降序排序，从参数 b 最大的边开始，算出最短路后删去该边，答案为每次最短路的最小值。

::::success[参考代码]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair< int, int >

const int N = 5005;

int n, m, ans = 1e18, dis[N];
bool vis[N];
struct Edge{
    int u, v, w, b;
    bool operator<(Edge x) const{return (b != x.b ? b < x.b : w < x.w);}
} e[N];

vector< pii > G[N];

void dijkstra(int free){
    for(int i = 1; i <= n; ++ i)
        dis[i] = 1e17, vis[i] = 0;
    dis[1] = 0;
    priority_queue< pii, vector< pii >, greater< pii > > q;
    q.push(make_pair(0, 1));
    while(!q.empty()){
        int u = q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto [v, i] : G[u]){
            int w = e[i].w;
            if(i == free)
                w = 0;
            if(dis[v] > dis[u] + w)
                dis[v] = dis[u] + w, q.push(make_pair(dis[v], v));
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
        cin >> e[i].u >> e[i].v >> e[i].w >> e[i].b;
    sort(e + 1, e + m + 1);
    for(int i = 1; i <= m; ++ i)
        G[e[i].u].push_back(make_pair(e[i].v, i)), G[e[i].v].push_back(make_pair(e[i].u, i));
    for(int i = m; i; -- i){
        dijkstra(i);
        ans = min(ans, dis[n]);
        G[e[i].u].pop_back();
        G[e[i].v].pop_back();
    }
    cout << (ans < (int)(1e17) ? ans : -1);

    return 0;
}

::::