C++(g++ 7.5.0) 解法, 执行用时: 578ms, 内存消耗: 55152K, 提交时间: 2023-01-17 10:29:11

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ld long double
#define FILE(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)
using namespace std;
const int N=1e6+5;
int dis[N],vis[N],re[N],fa[N],n,m,k,head[N],cnt=0;
struct edge {int v,w,nxt;} e[N];
struct node
{
	int dis,u;
	inline bool operator<(const node& oth)	const {return dis>oth.dis;}
};
struct graph
{
	int u,v,w;
	inline bool operator<(const graph& oth) const {return w<oth.w;}
} g[N];
inline void add(int u,int v,int w) {e[++cnt]={v,w,head[u]};head[u]=cnt;}
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void Dijkstra()
{
	priority_queue<node> q;
	cin>>k;
	memset(dis,0x3f,sizeof dis);
	for(int i=1,x;i<=k;++i)
	{
		cin>>x;
		dis[x]=0;
		q.push({0,x});
		re[x]=x;
	}
	while(q.size())
	{
		int u=q.top().u;
		q.pop();
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].v,w=e[i].w;
			if(vis[v])
				continue;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				re[v]=re[u];
				q.push({dis[v],v});
			}
		}
		vis[u]=1;
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m;
	for(int i=1,u,v,w;i<=m;++i)
	{
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	Dijkstra();
	int tot=0;
	for(int u=1;u<=n;++u)
	{
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].v,w=e[i].w;
			g[++tot]={re[u],re[v],dis[u]+dis[v]+w};
		}
	}
	for(int i=1;i<=n;++i)
		fa[i]=i;
	sort(g+1,g+tot+1);
	int idx=0,ans=0;
	for(int i=1;i<=tot;++i)
	{
		int u=find(g[i].u),v=find(g[i].v),w=g[i].w;
		if(u!=v)
		{
			++idx;
			fa[v]=u;
			ans=w;
		}
		if(idx==k-1)
			break;
	}
	cout<<ans;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 233ms, 内存消耗: 22936K, 提交时间: 2020-10-03 12:52:30

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,M=1e6+10;
int n,m,k,a[N],x[M],y[M],z[M],d[M],nr[N],f[N],vis[N],cnt,res;
int head[N],nex[M],to[M],w[M],tot;
struct node{int u,v,w;}t[M];
inline void add(int a,int b,int c){to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void Dijkstra(){
	priority_queue<pair<int,int> > q; memset(d,0x3f,sizeof d);
	for(int i=1;i<=k;i++) d[a[i]]=0,q.push({0,a[i]}),nr[a[i]]=a[i];
	while(q.size()){
		int u=q.top().second; q.pop();
		if(vis[u]) continue; vis[u]=1;
		for(int i=head[u];i;i=nex[i]) if(d[to[i]]>d[u]+w[i]){
			d[to[i]]=d[u]+w[i],nr[to[i]]=nr[u];
			q.push({-d[to[i]],to[i]});
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++) 
		scanf("%d %d %d",&x[i],&y[i],&z[i]),add(x[i],y[i],z[i]),add(y[i],x[i],z[i]);
	cin>>k;
	for(int i=1;i<=k;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) f[i]=i;
	Dijkstra();
	for(int i=1;i<=m;i++) if(nr[x[i]]!=nr[y[i]]) 
		t[++cnt]={nr[x[i]],nr[y[i]],d[x[i]]+d[y[i]]+z[i]};
	sort(t+1,t+1+cnt,[](node a,node b){return a.w<b.w;});
	for(int i=1;i<=cnt;i++){
		int x=find(t[i].u),y=find(t[i].v);
		if(x!=y) f[x]=y,res=t[i].w;
	}
	cout<<res;
	return 0;
}