Problem - 1149D - Codeforces

一点小思路

貌似有点问题。

首先保证图连通,发现点数为 $70$ 边数最多为 $200$。对于两种边权 $a, b$ 有一种想法就是让最短路包含在最小生成树中。或者说我们优先考虑边权小的边,先让其尽量成为生成树,能否直接暴力枚举端点 $i$,考虑暴力构建树。

是否有一个结论,就是我们考虑只使用 $a$ 边这样最短路肯定是可以在生成树上的。

如果仅仅使用 $a$ 边发现图是不连通的,我们考虑当前点 $i$ 所在的连通块。

现在本质上就是尝试暴力加入若干边,能否考虑使用 $b$ 边继续更新结果?

显然 $b$ 边只要能使图连通就是最小生成树了,考虑使用 $b$ 边使得 $1 \to i$ 的距离最短。

不妨考虑对于 $i$ 也进行一次最短路,是不是直接弗洛伊德更新呀?

就是每个点对之间打标记是否是通过了 $b$ 边进行更新即可。


$\tt solution$

考虑还是对于最小生成树,先考虑 $a$ 边构成的若干个连通块,之后只要使用 $b$ 边保证距离最小就行了,考虑需要保证是树的情况,所以一个点出去了之后就不会再回来,直接使用状压 $f(S, u)$ 表示已经走过的点集是 $S$,从 $1$ 到节点 $u$ 的最小距离,复杂度是 $O(2^n (n + m) \log (2^n(n + m)))$ 不是很行。

注意我们考虑的是一棵树,并且需要保证最短路径,考虑最短路的时候什么东西是可以省掉的,考虑状态 $S$ 表示点集,那么是否存在一些点集本身不会被额外更新?

发现如果一条 $b$ 边连接了相同连通块中的两个点,这条边本质上是不合法的,直接判掉就行了。还是相同的情况,如果有两条 $b$ 边通过一个中间点到达呢?发现 $2a < 2b$ 对于连通块大小小于 $4$ 的部分是不可能被更新到的。那么这样的连通块就不需要记录了。

所以我们只需要记录 $O(2^\frac{n}{4}n)$ 的状态就行了,考虑如何更新最短路。

参考 $\tt bfs$ 的操作,但是因为只有两种边所以一个点最多被更新到两次,考虑开两个队列存两种边进行更新即可。

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;
namespace Legendgod {
namespace Read {
// #define Fread
#ifdef Fread
const int Siz = (1 << 21) + 5;
char *iS, *iT, buf[Siz];
#define gc() ( iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iS == iT ? EOF : *iS ++) : *iS ++ )
#define getchar gc
#endif
template <typename T>
void r1(T &x) {
x = 0;
char c(getchar());
int f(1);
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
template <typename T, typename...Args>
void r1(T &x, Args&...arg) {
r1(x), r1(arg...);
}
#undef getchar
}

using namespace Read;

const int maxn = 2e5 + 5;
int n, m, A, B;
int head[maxn], cnt(1);
struct Edge {
int to, next, w;
}edg[maxn << 1];

void add(int u,int v,int w) {
edg[++ cnt] = (Edge) {v, head[u], w}, head[u] = cnt;
}

int bl[maxn], stot(0), siz[maxn], nstot(0), fl[maxn];

void dfs(int p,int c) {
bl[p] = c, ++ siz[c];
for(int i = head[p];i;i = edg[i].next) {
int to = edg[i].to, w = edg[i].w;
if(w == A && !bl[to]) dfs(to, c);
}
}

const int mxn = 70 + 5;
int f[(1 << 18) + 5][mxn];

queue< pair<int, int> > q[2];

int pd(const pair<int, int>& x, const pair<int, int>& y) {
if(f[x.first][x.second] < f[y.first][y.second]) return true;
else return false;
}

const int inf = 1e9;

signed main() {
int i, j;
r1(n, m, A, B);
for(i = 1; i <= m; ++ i) {
int u, v, w;
r1(u, v, w), add(u, v, w), add(v, u, w);
}
for(i = 1; i <= n; ++ i) if(!bl[i]) {
++ stot; dfs(i, stot);
fl[stot] = (siz[stot] > 3) ? ++ nstot : 0;
}
for(i = 1; i <= n; ++ i) for(j = 0; j < (1 << nstot); ++ j) f[j][i] = inf;
f[0][1] = 0;
q[0].push({0, 1}), q[1].push({0, 1});
while(!q[0].empty() || !q[1].empty()) {
pair<int, int> tmp;
if(q[1].empty() || (!q[0].empty() && pd(q[0].front(), q[1].front()))) tmp = q[0].front(), q[0].pop();
else tmp = q[1].front(), q[1].pop();
int S = tmp.first, u = tmp.second;
for(i = head[u];i;i = edg[i].next) {
int to = edg[i].to, w = edg[i].w;
if((bl[to] == bl[u] && w == B) || (fl[bl[to]] && ((S >> (fl[bl[to]] - 1)) & 1))) continue;
int nxt = (bl[to] == bl[u] || !fl[bl[u]]) ? S : (S | (1 << (fl[bl[u]] - 1)));
if(f[nxt][to] > f[S][u] + w) {
// printf("(%d, %d) = %d, S = %d, nxt = %d, vl = %d\n", u, to, w, S, nxt, f[nxt][to]);
f[nxt][to] = f[S][u] + w;
if(w == A) q[0].push({nxt, to});
else q[1].push({nxt, to});
}
}
}
int z = (1 << nstot);
for(i = 1; i <= n; ++ i) {
int res(0x3f3f3f3f);
for(j = 0; j < z; ++ j) res = min(res, f[j][i]);
printf("%d%c", res, " \n"[i == n]);
}
return 0;
}

}


signed main() { return Legendgod::main(), 0; }//