自动搬运

查看原文

来自洛谷，原作者为

	chenxi2009 身如柳絮随风扬。|粉福见专栏。|红名且勾支持互

搬运于2025-08-24 23:10:53，当前版本为作者最后更新于2025-03-07 22:28:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

$M=N-1$

图是一颗树，任意两点间路径唯一。从 $1$ 开始搜索，记录走到每一个点时的花费和当前温度。时间复杂度 $O(N)$。

$1\le c_i\le10$

可以把每个点拆成十个走最短路，新点中每个点表示对应到达旧点的某个温度。时间复杂度 $O(cN\log(cN)+cM)$。

每个点出边数量 $\le5$

还是拆点，每个点表示对应旧点出发时的温度。令 $\text{num}\leftarrow5$，时间复杂度 $O(\text{num}N\log(\text{num}N)+M)$。

无特殊限制

一条路径的总花费是这条路径上所有相邻的两条边温度之差。

考虑把每一条边看作一个新点，这个问题相当于是在每两条共点边之间连一条新边，新边长为两条边的温度差，求一条与 $1$ 相连的边到与 $N$ 相连的边的最短路。要额外累加与 $1$ 相连的边的 $c$。

这样连边是不行的，如果有一个菊花图显然任意两条边都是共点边，需要的新边数量量级达到 $M^2$。

我们需要从这一道题的性质上入手优化。发现新边长是新点权差，那么我们其实并不用给一个点所有的邻边都两两连新边，而是把这些边按温度排序，温度大小相邻的边之间连新边就行了，因为温度大小不相邻的边互相抵达可以通过温度在中间的点中转，而不影响消耗。

新边量级为 $O(M)$，再建一个超级源点导向 $1$ 的邻边，超级汇点由 $N$ 的邻边导向，跑这两点之间的最短路就好了。

时间复杂度 $O(M\log M)$。

还有一种做法，延续每个点出度 $\le5$ 的做法，还是拆点，和它相连的边的每个温度都拆出一个点，同一个旧点的温度相邻的新点之间连边，时间复杂度 $O(M\log M)$。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,w;
long long dis[300000];
bool vis[300000];
vector<pair<int,int>>e[300000],ne[300000];
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
inline void shortest_path(){//最短路板子 
	while(q.size()){
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(auto [v,w] : e[u]) if(dis[v] > dis[u] + w) q.push({dis[v] = dis[u] + w,v});
	}
	return;
}
int main(){
	memset(dis,0x3f,sizeof(dis));
	read(n,m);
	for(int i = 1;i <= m;i ++) read(u,v,w),ne[u].push_back({w,i}),ne[v].push_back({w,i});//旧边只需要保存温度和边编号 
	for(int i = 2;i < n;i ++){
		sort(ne[i].begin(),ne[i].end());//给一个点的邻边按温度排序 
		for(int j = 1;j < ne[i].size();j ++){//任意温度相邻的边之间连新边 
			e[ne[i][j].second].push_back({ne[i][j - 1].second,abs(ne[i][j].first - ne[i][j - 1].first)});
			e[ne[i][j - 1].second].push_back({ne[i][j].second,abs(ne[i][j].first - ne[i][j - 1].first)});
		}
	}
	for(auto i : ne[1]) e[0].push_back({i.second,i.first});//超级源点 0 号新点 
	for(auto i : ne[n]) e[i.second].push_back({m + 1,0});//超级汇点 M+1 号新点 
	dis[0] = 0,q.push({0,0});
	shortest_path();
	printf("%lld",dis[m + 1]);
	return 0;
}