C++ 解法, 执行用时: 107ms, 内存消耗: 5616K, 提交时间: 2021-12-12 19:34:38

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=2e5+10;
#define x first
#define y second
int h[N],ne[M],e[M],idx,w[M];
int dis[N];
int n,m;
bool st[N];
typedef pair<int,int> PII;
PII a[N]; 
void add(int a,int b,int c)
{
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}
void spfa()
{
	queue<int> q;
	q.push(0);
	memset(dis,0x3f,sizeof dis);
	dis[0]=0;
	st[0]=true; 
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		st[t]=false;
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(dis[j]>dis[t]+w[i])
			{
				dis[j]=dis[t]+w[i];
				if(!st[j])
				{
				q.push(j);
				st[j]=true;
				}
			}
		}
	}
}
int main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c); 
		add(b,a,c);
	}
	spfa();
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x;
		a[i].y=dis[i];
	}
	sort(a+1,a+1+n);
	long long ans=0;
	priority_queue<long long,vector<long long >,greater<long long >> heap;
	for(int i=1;i<=n;i++)
	{
		if(a[i].x>heap.size())
		{
			ans+=a[i].y;
			heap.push(a[i].y);	
		}	
		else 
		{
			if(a[i].y>heap.top())
			{
				ans-=2*heap.top();
				heap.pop();
				heap.push(a[i].y);
			 	ans+=a[i].y;
			}
		}
		
	} 
	cout<<ans<<endl;
	return 0;
}