自动搬运

查看原文

来自洛谷，原作者为

	SDqwq 少年何妨梦摘星，敢挽桑弓射玉衡。

搬运于2025-08-24 22:26:38，当前版本为作者最后更新于2020-11-23 23:33:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

博客食用更佳

前置芝士：最短路

Step 0 题意

• 一张 $n$ 个结点的无向带权图。

• 有 $k$ 个集合；第 $i$ 个集合可以表示为 $S_i=\{(T_1,W_1),(T_2,W_2),…,(T_{|S_i|},W_{|S_i|})\}$。

• 对于任何两对 $(T_i,W_i),(T_j,W_j)$ 在同一个集合里面，图中会形成一条连 $T_i$ 和 $T_j$ 的边，边权为 $W_i+W_j$。

Step 1 暴力

按照题意暴力建图，直接跑堆优化 dijkstra 即可。

时间复杂度：$\mathcal{O}((n+\sum|{S_i}^2|)\log \sum|{S_i}^2|)$

Step 2 正解

观察暴力解法后发现主要问题是边数太大。

• 考虑在每个集合 $S_i$ 中加入一个虚点 $x$。

• $x$ 向 $T_i$ 连接一条边权为 $W_i$ 的无向边 $(i\in[1,|S_i|])$。

执行完上述操作后可以发现仍然满足题目中 $<T_i,T_j>=W_i+W_j(i,j\in[1,|S_i|])$ 的要求。

此时边数为 $2\times\sum|S_i|$，可以承受。

时间复杂度：$\mathcal{O}((n+\sum|S_i|)\log\sum|S_i|)$

Step 3 代码

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, k, S, cnt, tot, T[400005], elast[600005];
ll W[400005], dis[600005];
bool vis[600005];

struct edge {
	int to, next;
	ll len;
} e[800005];

void add (int u, int v, ll w) {
	e[++cnt].to = v;
	e[cnt].len = w;
	e[cnt].next = elast[u];
	elast[u] = cnt;
}

struct node {
	ll dis;
	int id;
	node (ll _dis, int _id) {
		dis = _dis;
		id = _id;
	}
};

bool operator < (node x, node y) {
	return x.dis > y.dis;
}

priority_queue<node> pq;

void dijkstra (int x) {
	for (int i = 1; i <= tot; i++)
		dis[i] = inf;
	dis[x] = 0;
	pq.push(node(0, x));
	while (!pq.empty()) {
		node u = pq.top();
		pq.pop();
		if (vis[u.id])
			continue;
		vis[u.id] = true;
		for (int i = elast[u.id]; i != 0; i = e[i].next)
			if (dis[e[i].to] > dis[u.id] + e[i].len) {
				dis[e[i].to] = dis[u.id] + e[i].len;
				pq.push(node(dis[e[i].to], e[i].to));
			}
	}
}

int main () {
	scanf("%d %d", &n, &k);
	tot = n;
	for (int i = 1; i <= k; i++) {
		scanf("%d", &S);
		tot++;
		for (int j = 1; j <= S; j++) {
			scanf("%d %lld", &T[j], &W[j]);
			add(T[j], tot, W[j]);
			add(tot, T[j], W[j]);
		}
	}
	dijkstra(1);
	for (int i = 1; i <= n; i++)
		printf("%lld ", dis[i]);
	return 0;
}