P9377 [THUPC 2023 决赛] 百合

, , ,

同周赛 round 4

Description

https://www.luogu.com.cn/problem/P9377\

Solution

定义 $n^2$ 条权值为 $a_k$ 的边为附加边。

一个重要的性质是最多只会走 $k$ 条附加边。如果走多了，一定有多余的，因为两个点之间最多二进制相差 $k$。

枚举现在走了几条附加边。先跑一遍最短路。令 $f_{i,j}$ 表示节点 $i$ ，经过权值为 $a_j$ 的附加边之后，最短路为 $f_{i,j}+a_j$。

用类似于高位前缀和的写法一样，外层枚举不同的位置。内层找到两个点转移。

Code

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
#define int long long
#define maxn 300005
int k,m,s,n;
int f[maxn][18],dis[maxn];
int head=1,h[maxn];
struct yyy {
	int to,z,w;
	void add(int x,int y,int val) {
		to=y;z=h[x];h[x]=head;w=val;
	}
}a[maxn*2];
int w[18],vis[maxn];
priority_queue<pair<int,int> >q;
void dj(void) {
	int i,x;
//	q.push(mk(-dis[s],s));
	while (!q.empty()) q.pop();
	for (i=0;i<n;i++) q.push(mk(-dis[i],i)),vis[i]=0;
	while (!q.empty()) {
		x=q.top().se;q.pop();
		if (vis[x]) continue;vis[x]=1;
		for (i=h[x];i;i=a[i].z) if (dis[a[i].to]>dis[x]+a[i].w) {
			dis[a[i].to]=dis[x]+a[i].w;
			q.push(mk(-dis[a[i].to],a[i].to));
		}
	}
}
const int inf=1e12;
signed main(void){
	int i,x,y,z,o,j,k,l;
	read(k);read(m);read(s);n=1<<k;
	for (i=1;i<=k;i++) read(w[i]);
	for (i=1;i<=m;i++) {
		read(x),read(y),read(z);
		a[++head].add(x,y,z);
		a[++head].add(y,x,z);
	}
	memset(dis,0x3f,sizeof(dis));dis[s]=0;
	for (o=1;o<=k;o++) {
		dj();
		for (i=0;i<n;i++) for (j=1;j<=k;j++) f[i][j]=inf;
		for (i=0;i<n;i++) f[i][0]=dis[i];
		for (l=0;l<k;l++) 	
			for (i=0;i<n;i++) if ((i>>l)&1) {
				x=i,y=i^(1<<l);
				for (j=k;j>=1;j--) {
					f[x][j]=min(f[x][j],f[y][j-1]);
					f[y][j]=min(f[y][j],f[x][j-1]);
				}
			}
		for (i=0;i<n;i++) for (j=0;j<=k;j++) {
			dis[i]=min(dis[i],f[i][j]+w[j]);

		}
	}
	for (i=0;i<n;i++) printf("%lld ",dis[i]);  
	return 0;
}