最小距离

给定一张 $n$ 个点 $m$ 条边的带边权连通无向图，其中有 $p$ 个点是特殊点。

对于每个特殊点，求出它到离它最近的其它特殊点的距离。

$1 \le n,m \le 2 \times 10^5$，$2 \le p \le n$，$1 \le w \le 10^9$

首先，在 $\tt{Dijkstra}$ 前加入所有特殊点并把最短路设置为 $0$ ，跑的时候记录每个点 $x$ 的最短路是从哪里转移来的（$from_x$），这样跑完后就可以得出距离每个非特殊点最近的特殊点以及这个点的编号。

然后我们遍历所有边，对于这个边距离两个端点 $x$、$y$，如果 $from_x$ 和 $from_y$ 不同，就用 $dis_x+dis_y+w$ 更新 $from_x$ 和 $from_y$ 的答案。

考虑这样为什么是对的，假设离特殊点 $x$ 最近的特殊点点是 $y$，在边 $(u,v)$ 时两端的 $from$ 不同，即答案应当在这条边更新，我们假设这个算法是错误的，那么答案就不能更新，那么 $from_u \neq x$ 或 $from_v \neq y$。

• $ from_v = z \neq y $ ，则 dis[v][z] < dis[v][y] ，则 dis[x][z] < dis[x][y]，矛盾；
• $ from_u = w \neq x $ ，则 dis[u][w] < dis[u][y]，同理；

（第一种情况的图）

然后就没了。

#include <bits/stdc++.h>
using namespace std;
#define int long long

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
	return f ? -x : x;
}

#define N 400010
#define INF (1e17)
#define PII pair<int, int>

int n, m, p, a[N], hd[N], cnt = 1, dis[N], from[N], res[N], vis[N];

struct node {
	int y, v, to;
	node(int _y = 0, int _v = 0, int _to = 0) {
		y = _y, v = _v, to = _to;
	}
}e[N];

void addE(int x, int y, int v) {
	e[++ cnt] = node(y, v, hd[x]), hd[x] = cnt;
}

void Dij() {
	priority_queue<PII, vector<PII>, greater<PII> > pr;
	for (int i = 1; i <= n; i ++) dis[i] = INF;
	for (int i = 1; i <= p; i ++) {
		dis[a[i]] = 0, from[a[i]] = a[i];
		pr.push(make_pair(0, a[i]));
	}
	while (!pr.empty()) {
		int x = pr.top().second; pr.pop();
		if (vis[x]) continue; else vis[x] = 1;
		for (int i = hd[x]; i; i = e[i].to) {
			int y = e[i].y, v = e[i].v;
			if (dis[x] + v < dis[y]) {
				dis[y] = dis[x] + v;
				from[y] = from[x];
				pr.push(make_pair(dis[y], y));
			}
		}
	}
}

signed main() {
	n = read(), m = read(), p = read();
	for (int i = 1; i <= p; i ++) {
		a[i] = read();
	}
	for (int i = 1; i <= m; i ++) {
		int x = read(), y = read(), v = read();
		addE(x, y, v), addE(y, x, v);
	}
	Dij();
	for (int i = 1; i <= n; i ++) res[i] = INF;
	for (int i = 0; i <= cnt; i += 2) {
		int x = e[i ^ 1].y, y = e[i].y, v = e[i].v;
		if (from[x] == from[y]) continue;
		res[from[x]] = min(res[from[x]], dis[x] + dis[y] + v);
		res[from[y]] = min(res[from[y]], dis[x] + dis[y] + v);
	}
	for (int i = 1; i <= p; i ++) {
		printf("%lld ", res[a[i]]);
	}
	puts("");
	return 0;
}