自动搬运

查看原文

来自洛谷，原作者为

	MspAInt **

搬运于2025-08-24 21:17:30，当前版本为作者最后更新于2025-08-18 20:08:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一条路径的长度为 $\sum w-\max w+\min w$。

转换题意：一条路径的长度为，在总长的基础上任意选出一条边减去、一条边再加一次。求最短路。

本题关键在于：该转换不影响答案。

原因是，确定路径后最优方案一定是删去最大值、翻倍最小值，满足题意。

此处有重要思想：最优化问题放宽限制后，如果非法解必然较劣，那么这一转换是正确的。

那么就是一个很简单的 dp 了，令 $f_{u,a,b}$ 表示走到点 $u$，是否已经删去/增加一边的最短路。dijkstra 转移即可。

注意特判一条边的情况，此时增删等同于没有进行。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=2e5+10;
int n,m,q;
LL f[N][2][2];
bool vis[N*5];
vector<pair<int,int>>e[N];

void dijk(){
	priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>>q;
	memset(f,0x3f,sizeof(f));f[1][0][0]=0;
	q.push({0,1<<2});
	while(q.size()){
		int u=q.top().second;q.pop();
		if(vis[u])continue;vis[u]=1;
		int a=u>>1&1,b=u&1;u>>=2;
//		printf("%d %d %d\n",u,a,b);
		for(auto E:e[u]){
			int v=E.first,w=E.second;
			if(f[v][a][b]>f[u][a][b]+w)q.push({f[v][a][b]=f[u][a][b]+w,v<<2|b|a<<1});
			if(!a&&f[v][1][b]>f[u][0][b]+2*w)q.push({f[v][1][b]=f[u][0][b]+2*w,v<<2|b|2});
			if(!b&&f[v][a][1]>f[u][a][0])q.push({f[v][a][1]=f[u][a][0],v<<2|1|a<<1});
		}
	}
}

signed main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1,x,y,z;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		e[x].push_back({y,z});
		e[y].push_back({x,z});
	}
	dijk();
	while(q--){
		int i;scanf("%d",&i);
		printf("%lld\n",min(f[i][0][0],f[i][1][1]));
	}
	return 0;
}