$n$个点$m$条边的无向图, 带边权. 定义路径的某种长为 路径上边权的和 - 路径上最大边权 + 路径上最小边权. 求 1 到 其他点的这种路径最小长度.
$2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5$
拆点, 分层. 把一个点拆成4个, d[u][0][0] 表示没有走最小值或最大值, dp[u][0][1] 表示没有走最小值而走了最大值, dp[u][1][0] 表示走了最小值没有走最大值, dp[u][1][1] 表示走了最小值和最大值. 每层内的边权就是原来的边权, 并且是双向边; 而跨层的边权需要修改一下, 并且是单向边.
$00 \to 01, 10 \to 11$, 边权为$0$, $00 \to 10, 01 \to 11$, 边权是原来的两倍.
然后跑最短路.
由于最短路的性质和题目的特殊性质, 跑出来一定是减去最大值, 加上最小值的, 否则不是最短路.
分层图的话不用显式建图, 否则不仅很麻烦, 而且很难知道当前点有没有跑最大或最小. 用一个三元组(u, 0/1, 0/1)表示, 既方便了许多, 也能和 d[u][0/1][0/1] 对应. 同时记得 vis 也要写成这种形式.
答案就是 d[u][1][1].
代码里用了一点技巧把松弛写到了循环里, 当然拆开来写也不是不可以.
复杂度$O((m+n)\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
|
const int MAXN = 2e5+10;
struct Edge {
int to, next, w;
} edges[MAXN<<1];
int mm = 0, head[MAXN];
void add_edge(int u, int v, int w) {
edges[++mm] = Edge {v, head[u], w};
head[u] = mm;
}
void add_net(int u, int v, int w) {
add_edge(u, v, w);
add_edge(v, u, w);
}
int n, m;
struct Node {
int u, mn, mx;
LL dist;
bool operator < (const Node &N) const {
return dist > N.dist;
}
};
LL d[MAXN][2][2];
bool vis[MAXN][2][2];
void Dij(int s) {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
priority_queue<Node> Q;
d[s][0][0] = 0;
Q.push(Node{s, 0, 0, 0});
while (!Q.empty()) {
Node x = Q.top();
Q.pop();
int u = x.u, mx = x.mx, mn = x.mn;
if (!vis[u][mn][mx]) {
vis[u][mn][mx] = 1;
for (int i = head[u]; i; i = edges[i].next) {
Edge &e = edges[i];
for (int i = 0; i <= 1 - mn; i++)
for (int j = 0; j <= 1 - mx; j++) {
if (d[e.to][i|mn][j|mx] > d[u][mn][mx] + (1 - i + j) * e.w) {
d[e.to][i|mn][j|mx] = d[u][mn][mx] + (1 - i + j) * e.w;
Q.push(Node{e.to, i|mn, j|mx, d[e.to][i|mn][j|mx]});
}
}
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add_net(u, v, w);
}
Dij(1);
for (int i = 2; i <= n; i++)
printf("%lld ", d[i][1][1]);
puts("");
return 0;
}
|