C++(g++ 7.5.0) 解法, 执行用时: 385ms, 内存消耗: 23672K, 提交时间: 2023-01-01 20:10:53

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,a,b) for(int i=(a);i< (b);++i)
using namespace std;

const int N=2e5+7,M=N+N,INF=0x3f3f3f3f;
int n,m,p,fa[N],dist[N],st[N],ans[N],temp[N];
int e[M],ne[M],w[M],h[N],idx;

void add(int x,int y,int z)
{
	e[++idx]=y;
	w[  idx]=z;
	ne[ idx]=h[x];
	h[    x]=idx;
}

struct node{
	int id,dist;
	
	bool operator < (const node &W) const
	{
		return dist>W.dist;
	}
};

void dji()
{
	memset(st,0,sizeof st);
	memset(dist,0x3f,sizeof dist);
	
	priority_queue<node> q;
	rep(i,1,p)
	{
		dist[temp[i]]=0;
		q.push({temp[i],0});
	}
	
	while(!q.empty())
	{
		int u=q.top().id; q.pop(); 
		
		if(st[u]) continue;
		st[u]=1;
		
		for(int i=h[u];~i;i=ne[i])
		{
			int j=e[i];
			if(dist[j]>dist[u]+w[i])
			{
				dist[j]=dist[u]+w[i];
				fa[j]=fa[u];
				q.push({j,dist[j]});
			}
			else if(fa[j]!=fa[u])
			{
				ans[fa[u]]=min(ans[fa[u]],dist[j]+dist[u]+w[i]);
				ans[fa[j]]=min(ans[fa[j]],dist[j]+dist[u]+w[i]);
			}
		}
	}
}



signed main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m>>p;
	rep(i,1,p)
	{
		int x; cin>>x;
		ans[x]=LLONG_MAX;
		temp[i]=x;
		fa[x]=x;
	}
	
	rep(i,1,m)
	{
		int x,y,z; cin>>x>>y>>z;
		add(x,y,z); add(y,x,z);  
	}
	
	dji();
	
	rep(i,1,p) cout<<ans[temp[i]]<<" ";
	
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 478ms, 内存消耗: 22992K, 提交时间: 2020-05-04 10:47:30

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,M=N<<1;
int n,m,p,d[N],pre[N],res[N],x[N],vis[N];
int head[N],nex[M],to[M],w[M],tot;
inline void add(int a,int b,int c){to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;}
void Dijkstra(){
	priority_queue<pair<int,int> > q;	memset(d,0x3f,sizeof d);
	for(int i=1;i<=p;i++)	q.push({0,x[i]}),d[x[i]]=0,pre[x[i]]=x[i];
	while(q.size()){
		int u=q.top().second;	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];	q.push({-d[to[i]],to[i]}); pre[to[i]]=pre[u];
			}else if(pre[to[i]]!=pre[u]){
				res[pre[u]]=min(res[pre[u]],w[i]+d[u]+d[to[i]]);
				res[pre[to[i]]]=min(res[pre[to[i]]],w[i]+d[u]+d[to[i]]);
			}
		}
	}
}
signed main(){
	cin>>n>>m>>p;	memset(res,0x3f,sizeof res);
	for(int i=1;i<=p;i++)	scanf("%lld",&x[i]);
	for(int i=1,a,b,c;i<=m;i++)	scanf("%lld %lld %lld",&a,&b,&c),add(a,b,c),add(b,a,c);
	Dijkstra();
	for(int i=1;i<=p;i++)	printf("%lld ",res[x[i]]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 389ms, 内存消耗: 28268K, 提交时间: 2020-06-23 19:36:59

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

struct node
{
	long long x,h;
	bool operator<(const node &a)const
	{
		return a.h<h;
	}
}r,f;
vector<int>R[200005],W[200005];
priority_queue<node>Q;
int n,m,p,P[200005],V[200005];
long long D[200005],ans[200005];
int main()
{
    int i,j,k;
    scanf("%d%d%d",&n,&m,&p);
    for(i=1;i<=n;i++)D[i]=ans[i]=1e18;
    for(i=0;i<p;i++)scanf("%d",&P[i]),r.x=P[i],D[P[i]]=r.h=0,Q.push(r),V[P[i]]=P[i];
    while(m--)
    {
    	scanf("%d%d%d",&i,&j,&k);
    	R[i].push_back(j),R[j].push_back(i);
    	W[i].push_back(k),W[j].push_back(k);
	}
	while(!Q.empty())
	{
		f=Q.top(),Q.pop();
		if(D[f.x]<f.h)continue;
		for(i=0;i<R[f.x].size();i++)
		{
			j=R[f.x][i];
			if(f.h+W[f.x][i]<D[j])r.h=D[j]=f.h+W[f.x][i],r.x=j,Q.push(r),V[j]=V[f.x];
			else if(V[j]!=V[f.x])
			{
				ans[V[f.x]]=min(ans[V[f.x]],D[f.x]+D[j]+W[f.x][i]);
				ans[V[j]]=min(ans[V[j]],D[f.x]+D[j]+W[f.x][i]);
			}
		}
	}
	for(i=0;i<p;i++)printf("%lld ",ans[P[i]]);
    return 0;
}