[题解]CF1473E-Minimum Path

Posted on In

题意

给出一个\(n\)个点, \(m\)条边, 不含自环, 重边的带权无向图, 定义一条路径\(<v_1,v_2,...v_k>\)的权值为 \[ \sum_{i = 1}^k w_{v_i} - \max_{i = 1}^k\{w_{v_i}\} + \min_{i = 1}^k\{w_{v_i}\} \] 求从点1到其他所有点路径的最小权值

\(2 \leq n \leq 2e5,1 \leq m \leq 2e5,1 \leq w \leq 1e9\)

思路

原问题要求在权值中减去边权最大值, 加上边权最小值. 我们考虑将问题约束放宽: 可以减去和加上任意一条边的边权.

可以发现, 在最短路径中, 减去的必定是边权最大值, 而加上的必定是边权最小值(可用反证法证明), 即放宽后的问题与原问题等价.

求解该问题可以用分层图最短路. 由于必须加上和减去一条边的边权, 故求解最短路径时可能有以下三种情况:

  1. 先减去边X(图A), 再加上边Y(图B)
  2. 先加上边X(图C), 再减去边Y(图D)
  3. 加上和减去同一条边X (图S, 相当于原图最短路)
pic1.png

建图时每层原图为无向边，连接两层图之间的边为有向边, 具体细节见代码. 从1开始跑Dijkstra, 图S, B , D的最小值即为答案.

时间复杂度: \(O(m\log n)\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> node;
#define endl '\n'
const int N = 2e5+1;
const int maxn = N*6+10;
const int maxm = maxn*6;
const ll INF = 1e17;
int head[maxn],cnt;
bool vis[maxn];
ll dis[maxn];
struct Edge{
	int f,t;
	ll w;
	int next;
	Edge(int f = 0,int t = 0,ll w = 0,int next = 0):f(f),t(t),w(w),next(next){}
}edge[maxm];
void addedge(int f,int t,ll w){
	edge[cnt] = Edge(f,t,w,head[f]);
	head[f] = cnt++;
}
void dijkstra(int s){
	for(int i = 1;i < maxn;i++)dis[i] = INF;
	dis[s] = 0;
	priority_queue<node,vector<node>,greater<node> >pq;
	pq.push({0,s});
	while(!pq.empty()){
		int u = pq.top().second;
		pq.pop();
		if(vis[u])continue;
		vis[u] = 1;
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].t;
			ll w = edge[i].w;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				if(!vis[v]){
					pq.push({dis[v],v});
				}
			}
		}
	}
}
void add(int f,int t,int w){
	addedge(f,t,w);
	addedge(t,f,w);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(head,-1,sizeof(head));
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		int f,t,w;
		cin >> f >> t >> w;
		//+0:ori
		//+N:sub first
		//+2*N:sub -> add
		//+3*N:add first
		//+4*N:add -> sub
		add(f,t,w);
		add(f+N,t+N,w);
		add(f+2*N,t+2*N,w);
		add(f+3*N,t+3*N,w);
		add(f+4*N,t+4*N,w);
		addedge(f,t+N,0);//sub
		addedge(t,f+N,0);
		addedge(f+N,t+2*N,2*w);//add
		addedge(t+N,f+2*N,2*w);
		addedge(f,t+3*N,2*w);//add
		addedge(t,f+3*N,2*w);
		addedge(f+3*N,t+4*N,0);//sub
		addedge(t+3*N,f+4*N,0);
	}
	dijkstra(1);
	for(int i = 2;i <= n;i++){
		cout << min({dis[i+2*N],dis[i+4*N],dis[i]}) << " ";
	}
	return 0;
}