本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-12 17:15:16

思路

复杂度中认为 $n,m,k$ 同级。

发现打开第一个传送门后，打开新传送门的过程类似于 Prim 求最小生成树，也就是找到已打开点集和未打开点集之间的最短路径，然后直接传送到已打开的 $S$ 点，再走到未打开的 $T$ 点并打开。

显然中间走的路径是最短路，所以对 $k$ 个点建完全图，边权为两个点在原图上的最短路径。之后在 $k$ 个点的新图上跑最小生成树，答案即为最小生成树的权值和加上起点到传送门的最短距离。时间复杂度瓶颈在预处理两点之间最短路径，用 Dijkstra 的话大概是 $O(n^2\log n)$。

考虑减少新图中的边数，设 $p_i$ 表示离 $i$ 最近的传送门编号，$dis_i$ 为距传送门的距离。那么对于一条权值为 $w$ 的边 $(u,v)$，在新图上建边 $p_u\to p_v$，边权为 $dis_u+dis_v+w$，这样就能包含所有最终最小生成树中的边。

笔者太菜了，完全想不出这个方法，读了官方题解之后自己证明如下：

以下设 $d_{i,j}$ 表示点 $i$ 和点 $j$ 之间的最短路径长度，两个集合即为上述已开启和未开启的点集。

对于最终在最小生成树中的一条边（原图中的路径） $S\to T$，若路径前半部分的 $p_i=S$，后半部分的 $p_i=T$，那么路径上一定存在一条边 $(u,v)$ 满足 $p_u=S$ 且 $p_v=T$。现在只需要证明路径上 $p$ 的情况如此即可。

使用反证法，假设 $S\to u$ 的路径上有点 $x$ 使得 $p_x\ne S$，设 $p_x=E$，那么 $x\to u$ 的路径上点的 $p$ 均为 $E$。

若 $E$ 与 $S$ 属于同一集合，与 $T$ 属于不同集合，那么由于 $d_{E,u}\le d_{S,u}$，可以取 $E \to T$ 这条路径。

否则 $E$ 与 $S$ 属于不同集合，由于路径的包含和 $p$ 数组的定义，有 $d_{E,x}\le d_{E,u}\le d_{S,u}\le d_{u,T}\le d_{x,T}$，最终得到 $d_{E,x}\le d_{T,x}$，可以取 $S\to E$ 这条路径。

$v\to T$ 路径上的情况相同。式子比较抽象，可以结合下面丑陋的图。

所以最终只需要以 $k$ 个点为起点用 Dijkstra 跑单源最短路，预处理出 $p,dis$ 数组即可，时间复杂度降为 $O(n\log n)$。

代码

#include<iostream>
#include<vector> 
#include<queue>
#include<algorithm>
#define pii pair<int,int>
#define int long long
using namespace std; 
const int N=1e5+10;
const int inf=2e18;
int n,m,k,res,p[N],to[N],dis[N],tu[N],tv[N],tw[N],f[N];
bool vis[N];
vector <pii> edge[N];
struct nod {int u,v,w;}ne[N];
bool cmp(nod ta,nod tb) {return ta.w<tb.w;}
priority_queue <pii> q;
int finds(int x) {return (f[x]==x?x:f[x]=finds(f[x]));}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1,u,v,w;i<=m;i++)
	{
		cin>>u>>v>>w,tu[i]=u,tv[i]=v,tw[i]=w;
		edge[u].push_back({v,w}),edge[v].push_back({u,w});
	}
	for(int i=1;i<=n;i++) dis[i]=inf,to[i]=-1;
	cin>>k;
	for(int i=1;i<=k;i++) cin>>p[i],to[p[i]]=i,dis[p[i]]=0,q.push({0,p[i]});
	while(q.size())
	{
		int u=q.top().second; q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(pii te:edge[u])
		{
			int v=te.first,w=te.second;
			if(dis[v]>dis[u]+w) dis[v]=dis[u]+w,to[v]=to[u],q.push({-dis[v],v});
		}
	} \/\/Dijkstra 预处理 
	for(int i=1;i<=m;i++) ne[i]={to[tu[i]],to[tv[i]],dis[tu[i]]+dis[tv[i]]+tw[i]};
	sort(ne+1,ne+1+m,cmp);
	for(int i=1;i<=k;i++) f[i]=i;
	for(int i=1;i<=m;i++)
	{
		int fu=finds(ne[i].u),fv=finds(ne[i].v),w=ne[i].w;
		if(fu!=fv) f[fu]=fv,res+=w;
	} \/\/建新图 Kruskal 跑最小生成树 
	cout<<res+dis[1];
	return 0;
}