CF1473E Minimum Path 题解（最短路，分层图最短路，较重要的套路）

题目描述：

题目

分析：

         题目是要让我们求从 $1$ 出发，到 $i$ 的路径的最小权值。其中路径的权值定义为 路径上所有的边权和 减去最大边权 加上最小边权。这里有一个很秒的转化：可以把一条路径的权值理解为 必须将路径上的任意一条边不算代价，任意一条边算 $2$ 倍代价，问起点到终点的最小路径权值。在这样的理解下，最小权值一定是减去最大边权 加上最小边权，因此这样的转化是正确的。

         这样我们就把 对两条极值边的贡献方式转化成了所有边的贡献方式。看起来更加统一，也更好处理了。

         对于这种 有 $k$ 次机会改变边权 的最短路问题，都可以用 分层图最短路 解决。对于本题，由于 这两种特殊代价没有先后顺序，因此我们需要建 $4$ 层图：每层图内正常边权，第一层图向第二层图连边权为 $0$ 的边，第一层图向第三层图连边权为 $2\times w$ 的边，第二层图向第四层图连边权为 $2\times w$ 的边，第三层图向第四层图连边权为 $0$ 的边。

         有一个细节需要注意：查询答案时需要询问第一层和第四层较小的答案。这是因为一条路径只有一条边时第四层图中的答案会偏大，这是由于走了多余的边导致的。而由于 $max$ 和 $min$ 相等，所以正好抵消，第一层的答案时正确的。对于不止有一条边的路径，显然第四层的答案会更优，因此也满足题意。

CODE：

// 首先将问题转化：-max +min 转化为可以将任意一条边不算权值，将任意一条边权值计算两次取最优，这样的话最优答案一定是减去 max 加上 min 
// 这样对两条极值边的限制就转化为了对所有边的限制
// 这样就变成了分层图的板子 
// 需要注意的是这两种操作的顺序是任意的，因此建图时必须将两种可选择的顺序都体现出来
// 建图：第一层->第三层 2w  第一层->第二层 0  第三层->第四层 0  第二层->第四层 2w 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int M = 2e5 + 10;
typedef long long LL;
int n, m, u, v, head[N * 4], tot;
LL w, dis[N * 4];
struct edge {
	int v, last; LL w;
}E[M * 8 * 2];
void add(int u, int v, LL w) {
	E[++ tot].v = v;
	E[tot].last = head[u];
	E[tot].w = w;
	head[u] = tot;
}
bool vis[N * 4];
struct state {
	int x; LL w;
	friend bool operator < (state a, state b) {
		return a.w > b.w;
	}
};
priority_queue< state > q;
void dijkstra(int s) {
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0; q.push((state) {s, dis[s]});
	while(!q.empty()) {
		state t = q.top(); q.pop();
		int x = t.x; LL w = t.w;
		if(vis[x]) continue;
		vis[x] = 1; 
		for(int i = head[x]; i; i = E[i].last) {
			int v = E[i].v; LL w = E[i].w;
			if(dis[v] > dis[x] + w) {
				dis[v] = dis[x] + w;
				q.push((state) {v, dis[v]});
			}
		}
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++ ) {
		scanf("%d%d%lld", &u, &v, &w);
		for(int j = 0; j <= 3; j ++ ) {
			add(u + n * j, v + n * j, w);
			add(v + n * j, u + n * j, w);
		}
		add(u, v + n * 2, 2LL * w); add(v, u + n * 2, 2LL * w);
		add(u, v + n, 0); add(v, u + n, 0);
		add(u + n, v + n * 3, 2LL * w); add(v + n, u + n * 3, 2LL * w);
		add(u + n * 2, v + n * 3, 0); add(v + n * 2, u + n * 3, 0);
	}
	dijkstra(1);
	for(int i = 2; i <= n; i ++ ) 
		printf("%lld ", min(dis[i], dis[i + 3 * n]));
	return 0;
}