博客

题目描述

给定一个 nn 个点，mm 条有向边的带非负权图，请你计算从 ss 出发，到每个点的距离。

数据保证你能从 ss 出发到任意点。

输入格式

第一行为三个正整数 n, m, sn,m,s。 第二行起 mm 行，每行三个非负整数 u_i, v_i, w_iu

i

​

,v

i

​

,w

i

​

，表示从 u_iu

i

​

到 v_iv

i

​

有一条权值为 w_iw

i

​

的有向边。

输出格式

输出一行 nn 个空格分隔的非负整数，表示 ss 到每个点的距离。

注意本代码第27行，千万不能落，否则就会TLE 50

#include<bits/stdc++.h>
using namespace std;
const long long maxn=2e5+5;
priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > > que;
long long vis[maxn],dis[maxn],n,m,root,cnt,head[maxn];
struct T
{
	long long v,nxt,to;
}edge[2*maxn];
void add(long long from,long long to,long long value)
{
	edge[++cnt].nxt=head[from];
	edge[cnt].to=to;
	edge[cnt].v=value;
	head[from]=cnt;
} 
void dij()
{
	for(int i=1;i<=n;i++) dis[i]=99999999999999;
	memset(vis,0,sizeof(vis));
	dis[root]=0;
	que.push(make_pair(dis[root],root));
	while(!que.empty())
	{
		long long now=que.top().second;
		que.pop();
		if(vis[now]) continue;
		for(long long i=head[now];i;i=edge[i].nxt)
		{
			long long to=edge[i].to;
			if(dis[to]>dis[now]+edge[i].v)
			{
				dis[to]=dis[now]+edge[i].v;
				if(!vis[to])
				{
					que.push(make_pair(dis[to],to));
					vis[now]=1;
				}
			}
		}
	}
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&root);
	for(long long i=1;i<=m;i++)
	{
		long long a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		add(a,b,c);
	}
	dij();
	for(long long i=1;i<=n;i++)
	printf("%lld ",dis[i]);
}