题解：P4524 [COCI2017-2018#4] Ceste

· · 题解

观前注意

本篇题解是乱搞题解，具有错误的复杂度。如果要学习正经的解题思路可以选择跳过本篇题解。

解题思路

发现这个东西我们直接跑传统单源最短路是不对的，因为一个 dis 数值显然难以完全描述全部两种边权的大小关系。如何把这个东西描述完全？

我们考虑到达点 u 的 \sum T 和 \sum C 取何值时才有可能对最短路径做贡献，发现当存在另一组 \sum T 和 \sum C 均小于现取值时这个取值显然无意义，换言之，我们只需要对每个点维护一个凸包即可囊括所有可能的更新情况。

于是我们直接跑最短路，把传统最短路的入队条件改为对应 \sum T,\sum C 是否在这个点的凸包上，然后一样更新最短路即可。

这个东西的最坏复杂度是 O(Vnm \log Vnm)，但是在一般的数据下凸包的点数显然远小于上界，跑得很快（时限 2.5s，最慢点 414ms），于是顺利通过了该题。

具体实现细节看代码。

AC 代码

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=2005,INF=1e16;

int n,m; 
vector<tuple<int,int,int>> vec[N];

struct Node {
    int u,w1,w2;
    inline bool operator < (const Node& b) const {
        return w1*w2 > b.w1*b.w2;
    }
};

priority_queue<Node> que;
int dis[N];
set<pair<int,int>> S[N]; // 维护凸包 

void dij(int s) {
    que.push({s,0,0});
    memset(dis,63,sizeof(dis));
    S[s].insert({0,0});

    int v1,v2;
    while(!que.empty()) {
        auto [u,p,q]=que.top();
        que.pop();

        if(!S[u].count({p,q})) continue;
        dis[u]=min(dis[u],p*q);

        for(auto& [v,w1,w2]:vec[u]) {
            v1=p+w1,v2=q+w2;
            auto p=S[v].lower_bound({v1,v2});
            if(p!=S[v].begin() && (*prev(p)).second<v2) continue; // 无法更新
            while(p!=S[v].end() && (*p).second>v2) p=S[v].erase(p);
            S[v].insert({v1,v2});
            que.push({v,v1,v2});
        }
    }
}

signed main() {
    cin >> n >> m;

    int u,v,w1,w2;
    for(int i=1;i<=m;++i) {
        cin >> u >> v >> w1 >> w2;
        vec[u].push_back(make_tuple(v,w1,w2));
        vec[v].push_back(make_tuple(u,w1,w2));
    }

    dij(1);

    for(int i=2;i<=n;++i) {
        if(dis[i]<=INF) cout << dis[i] << endl;
        else cout << -1 << endl;
    }
    return 0;
}