自动搬运

查看原文

来自洛谷，原作者为

	dingcx 不如回头再看一眼题面

搬运于2025-08-24 22:24:53，当前版本为作者最后更新于2022-04-09 15:25:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这里给出一篇更为通俗易懂的题解，算是对其它题解的补充说明吧。

思路

如果暴力枚举翻转每条边，每个进行一遍 dijkstra，复杂度 $O(n^2m)$，需要优化。

本题的优化方法是减少 dij 的使用次数。因为许多边的翻转其实不影响最短路的长度，此时就不需要再调用 dij 求一边长度了，可以节省时间。

那么边可以分为两类，一种边翻转后对最短路长度产生影响，称为“关键边”，否则不产生影响就不是关键边。

对于每个关键边，需要修改一下边并重新调用 dij 计算最短路，因为 dij 是 $n^2$ 的，所以关键边的个数需要限制到 $O(n)$ 级别；对于非关键边，因为有 $m$ 条，需要在 $O(n)$ 内求出路径长度，当然这道题比较神奇，可以 $O(1)$ 就求出。

考虑如何处理非关键边，这里直接上结论：选择翻转边 $(u,v)$ 的最终代价为 $D+\min(dis(1,n),dis(1,v)+C+dis(u,n))+\min(dis(n,1),dis(n,v)+C+dis(u,1))$。（$dis(u,v)$ 就是 $u \to v$ 的最短距离）

下面说明为什么这个结论是对的。（这里也是其它题解可能讲的不是很清楚的地方，当然这里确实不好说，因为关键边和非关键边是相互依存相互促进的，接下来这一大段话也会顺便讲掉如何处理关键边。）

首先需要给出关键边的定义（上面的那个不是定义，只是一个大概的理解）：在 $1\to i,i \to n,n \to i,i \to 1 (1 \le i \le n)$ 的其中一个的最短路径上的边。

容易发现，从一个定点出发（或一个定点结束）到其它每个点的最短路径构成一棵树（如果有两条长度相同的就随便选一条），这样关键路径的条数就是上面这 $4$ 棵最短路径树上的边，是 $O(n)$ 级别，满足要求。

有了定义，再回头看那个式子，这里就只看 $1 \to n$ 了，因为 $n \to 1$ 也同理。翻转边 $(u,v)$ 后 $1 \to n$ 代价是 $\min(dis(1,n),dis(1,v)+C+dis(u,n))$。

证明这个是对的，其实就需要两步：为什么能取到，为什么是最小的。式子中的 $dis(1,n)$ 就是选择不经过 $(u,v)$ 的翻转边，（这里可能有人会问，为什么不经过这条边还要翻转，原因是可能去的时候不经过，回来的时候就需要经过了。）因为 $(u,v)$ 不是关键边，所以 $dis(1,n)$ 不会改变，可以直接用；式子中的 $dis(1,v)+C+dis(u,n)$ 就是选择经过 $(u,v)$ 的翻转边，因为不是关键边，翻转 $(u,v)$ 不会改变 $1$ 到任何点、任何点到 $n$ 的最短路径长度，所以 $dis(1,v),dis(u,n)$ 不会改变，然后因为要经过这条边，所以一定是先最短路径走到 $v$，再用这条边到 $u$，然后走最短路径到 $n$。以上两种情况（走与不走翻转边）包含了所有情况，而它们各自是自己情况的最小，所以它们的较小值就是最终的最小值。

有了这样的结论，只需要先预处理出 $dis(1,i),dis(i,n),dis(n,i),dis(i,1)$，便可以 $O(1)$ 计算翻转非关键边的答案。

至此，我们分当前翻转的边是不是关键边两种情况进行了处理，这道题也就大功告成了，总复杂度 $O(n^3+m)$。

写法的技巧和细节

这道题的代码并不好写，不然我也不至于调 2h，于是在这里总结了一些写法上的小技巧和容易出错的细节。

dij 不要用优先队列优化，那样是 $m \log n$，不如暴力的 $n^2$。同时别用邻接表，用邻接矩阵，方便翻转边。

关键边的求法：把每个点最终的 $dis$ 是从哪条边转移过来的记录一下，这些边就是关键边。

如何求 $dis(i,n),dis(i,1)$：建立反图，就可以以 $n,1$ 为起点求了。不过因为这道题是邻接矩阵，方便操作，也可以在 dij 中做手脚，详细可以看下面的代码。

如何处理重边：邻接矩阵是显示不出来重边的，所以在求邻接矩阵时，需要保留边权最小的边，不过这还没完，因为边权最小的边可能被翻转掉，所以还需要记录边权第二小的边，这样可以在边权最小的边翻转后暂时顶替它的位置。但处理重边需要注意，边权大的边只能在邻接矩阵中被忽略，但也需要被存起来，因为这条边的 $D$ 可能很小，把这条边翻转得到的答案可能更优，也就是说在翻转边的时候这条边也需要被考虑进来。

以上细节可能不全，那下面的代码和注释应该能解决你的所有疑惑。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN=210,MAXM=5e4+10;
int n,m,from[MAXN]; //from[i] 表示最终的 dis[i] 是从哪条边转移来的
ll c[MAXN][MAXN],c2[MAXN][MAXN]; //邻接矩阵的最小值和次小值
ll dist[4][MAXN],tdis[MAXN]; //dist[0,1,2,3] 分别是 1->i,i->n,n->i,i->1 的最短距离
bool vis[MAXN],key[MAXN][MAXN],used[MAXN][MAXN]; //key 记录关键边
struct Edge{
	int u,v;ll C,D;
}e[MAXM];
int read(){
	int num=0,sign=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')sign=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	return num*sign;
}
void dij(int st,ll *dis,int op){ //op=0 是正图，op=1 是反图，op=2 表示翻转一条边的正图
	memset(vis,0,sizeof(vis));
	for(int i=0;i<=n;i++) dis[i]=2e18;
	dis[st]=0;
	while(1){
		int u=0;
		for(int i=1;i<=n;i++)
			if(!vis[i]&&dis[u]>dis[i]) u=i;
		if(!u) break;
		vis[u]=1;
		for(int i=1;i<=n;i++){
			ll w=(op==1)?c[i][u]:c[u][i]; //处理正图和反图
			if(!vis[i]&&dis[u]+w<dis[i]){
				dis[i]=dis[u]+w;
				if(op<2) from[i]=u; //记录当前转移来的边，但这未必是最终的
			}
		}
	}
	if(op<2) for(int i=1;i<=n;i++) key[from[i]][i]=1; //记录关键边
}
int main(){
	n=read(),m=read();
	memset(c,0x3f,sizeof(c)),memset(c2,0x3f,sizeof(c2));
	for(int i=1;i<=n;i++) c[i][i]=0;
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),C=read(),D=read();
		e[i].u=u,e[i].v=v,e[i].C=C,e[i].D=D;
		if(c[u][v]>C) c2[u][v]=c[u][v],c[u][v]=C; //更新邻接矩阵最大值和次大值
		else if(c2[u][v]>C) c2[u][v]=C; //更新次大值
	}
	dij(n,dist[1],1),dij(1,dist[3],1); //预处理 4 个最短路
	dij(1,dist[0],0),dij(n,dist[2],0);
	ll ans=dist[0][n]+dist[2][1]; //不翻转边
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v;ll C=e[i].C,D=e[i].D;
		if(key[u][v]&&C==c[u][v]&&!used[u][v]){ //是关键边
			ll tmpu=c[u][v],tmpv=c[v][u];
			c[v][u]=min(c[v][u],C); //翻转边 (u,v)
			c[u][v]=(c[u][v]==C)?c2[u][v]:c[u][v]; //如果最小边被翻转，次小边顶替
			ll sum=D;
			dij(1,tdis,2);sum+=tdis[n]; //重算距离
			dij(n,tdis,2);sum+=tdis[1];
			ans=min(ans,sum); //更新答案
			c[u][v]=tmpu,c[v][u]=tmpv; //回溯
			used[u][v]=1;
		}
		else ans=min(ans,(ll)D+
			min(dist[0][n],dist[0][v]+C+dist[1][u])+
			min(dist[2][1],dist[2][v]+C+dist[3][u])); //套公式
	}
	printf("%lld\n",(ans>=1e18)?-1:ans);
	return 0; //华丽结束
}

不要忘记点赞~