自动搬运

查看原文

来自洛谷，原作者为

	TLEWA 一袋可爱的猫粮喵！

搬运于2025-08-24 22:01:01，当前版本为作者最后更新于2024-11-01 16:13:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

观前注意

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

解题思路

发现这个东西我们直接跑传统单源最短路是不对的，因为一个 $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;
}