题解 P6880 [JOI 2020 Final] オリンピックバス

洛谷。

题意

应该显然，注意最多只能翻转一条边，并且可以不翻转。

分析

首先观察数据范围 \(2\le N \le 200\)，\(1\le M \le 5\times 10^4\)，可以发现我们的 \(N\) 和 \(M\) 并不是同级的，因此，在众多的最短路算法中，我们应当选择不加堆优化的 dijkstra 算法，并且使用邻接矩阵，这是 \(O(n^2)\) 的时间复杂度，加入使用了堆优化或者使用邻接表，这就会使我们的最短路的时间变大。

接下来就是这道题比较巧妙的地方了，我们都知道 \(M\le 1000\) 的暴力怎么打，使用不加堆优化的迪杰，加上枚举翻转的边，时间复杂度是 \(O(M\times N^2)\)。但是这 \(m\) 次最短路并不是都是必须的，首先，假如我们枚举的这条边并不在 \(1\) 到 \(n\) 或 \(n\) 到 \(1\) 的最短路当中，那么翻转场此边并不会影响原来的路径的大小，但是我们的最短路可能会因此发生改变，不过只需要用原来 \(1\) 到 \(v\) 的最短路加上 \(u\) 到 \(n\) 的最短路加上翻转的边，与原最短路取小值即可。

那么在原最短路径的边呢，没有什么高大上的算法，直接和暴力一样即可。

接下来分析一下时间复杂度，我们的暴力是 \(O(n^2)\)，不在最短路上的取答案是 \(O(1)\)，而最短路径上的边数，最多只有 \(O(n)\)。

注意，这里的最短路径上的边，是指确定的一条路径，这条路径可以用记转移来的结点，也就是最短路径树解决，而不是可能出现在最短路径上的边。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e2+5;
const int M = 5e4+5;
const int INF = 0x3f3f3f3f3f3f;
inline int read() {
	int x;
	scanf("%lld",&x);
	return x;
}
int n, m;
struct Edge {
	int u,v,c,d;
} edge[M];

int lj[N][N],g[N][N],mark[N],dis[5][N],fa[5][N],vis[2][N][N];
//dis[0] 1 正  dis[1] n 正  dis[2] 1 反 dis[3] n 反 dis[4] ls

inline void dj(int st,int *dis,int *fa) {
	for(int i=1; i<=n; ++i) dis[0]=dis[i]=INF,mark[i]=fa[i]=0;
	dis[st]=0;
	while(1) {
		int now=0;
		for(int i=1; i<=n; ++i) if(!mark[i]&&dis[i]<dis[now]) now=i;
		if(!now) break;
		mark[now]=1;
		for(int i=1; i<=n; ++i) if(dis[i]>dis[now]+lj[now][i]) dis[i]=dis[now]+lj[now][i],fa[i]=now;
	}
	return ;
}

signed main() {
	n=read(),m=read();
	for(int i=1; i<=m; ++i) edge[i]=<%read(),read(),read(),read()%>;
	memset(lj,0x3f,sizeof lj),memset(g,0x3f,sizeof g);
	for(int i=1; i<=m; ++i) {
		int u=edge[i].u,v=edge[i].v,c=edge[i].c;
		g[u][v]=min(g[u][v],c);
		if(g[u][v]<lj[u][v]) swap(g[u][v],lj[u][v]);
	}
	dj(1,dis[0],fa[0]),dj(n,dis[1],fa[1]);
	for(int i=1; i<=n; ++i) for(int j=i; j<=n; ++j) swap(lj[i][j],lj[j][i]);
	dj(1,dis[2],fa[2]),dj(n,dis[3],fa[3]);
	for(int i=1; i<=n; ++i) for(int j=i; j<=n; ++j) swap(lj[i][j],lj[j][i]);
	int res=dis[0][n]+dis[1][1];
	if(dis[0][n]<INF) for(int now=n; now; now=fa[0][now]) vis[0][fa[0][now]][now]=1;
	if(dis[1][1]<INF) for(int now=1; now; now=fa[1][now]) vis[1][fa[1][now]][now]=1;
	for(int i=1; i<=m; ++i) {
		int u=edge[i].u,v=edge[i].v,c=edge[i].c,d=edge[i].d;
		int len1=lj[u][v],len2=lj[v][u];
		if(lj[u][v]==c) lj[u][v]=g[u][v];
		lj[v][u]=min(lj[v][u],c);
		int tot=d;
		if(vis[0][u][v]) dj(1,dis[4],fa[4]),tot+=dis[4][n];
		else tot+=min(dis[0][n],dis[0][v]+dis[3][u]+c);

		if(vis[1][u][v]) dj(n,dis[4],fa[4]),tot+=dis[4][1];
		else tot+=min(dis[1][1],dis[1][v]+dis[2][u]+c);
		
		res=min(res,tot);
		lj[u][v]=len1,lj[v][u]=len2;
	}
	cout<<(res>=INF?-1:res)<<"\n";
	return 0;
}

总结起来，这道题利用了最短路的边数小，以及不加堆优化的 dijkstra，这两个平时并不多用的性质，是一道最短路好题。