CF938D 多源最短路

题目

给你$N$个点, 有点权$a[i]$, 有$M$条边, 每条边有边权$c[i]$, 对于每个$i$ ,$j$ 为任意点,求$min(dist(i,j)*2+a[j])$

$N,M \leq 2*10^5$

分析

题目相当于求每个点到图中的最短路,既多源最短路.可以利用堆优化的dijkstra求得.因为堆顶每次都为到改点的距离最小值,我们每次取出堆顶,然后向相邻点扩展即可.

代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
typedef pair<long long,int> P;
const int MAXN=2e5+7;
const long long INF=1e17;
priority_queue<P,vector<P>,greater<P> >q;
vector<P>G[MAXN];
long long  cost[MAXN],d[MAXN];
int done[MAXN];
int main(){
	int N,M;scanf("%d%d",&N,&M);
	for(int i=0;i<M;++i){
		int a,b;long long c;
		scanf("%d%d%I64d",&a,&b,&c);
		G[a].push_back(P(2*c,b));
		G[b].push_back(P(2*c,a));
	}
	for(int i=1;i<=N;++i){
		scanf("%I64d",&cost[i]);
		q.push(P(cost[i],i));
	}
	for(int i=1;i<=N;++i)d[i]=INF,done[i]=0;

	while(!q.empty()){
		P p=q.top();q.pop();
		int u=p.second;
		if(done[u])continue;
		done[u]=1;
		d[u]=p.first;
		int len=G[u].size();
		for(int i=0;i<len;++i){
			int v=G[u][i].second;
			q.push(P(G[u][i].first+d[u],v));
		}
	}

	for(int i=1;i<=N;++i){
		printf("%I64d ",d[i]);
	}
	return 0;
}