网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

【YBTOJ】单源最短路径

2021/4/17 7:50:15 人评论

思路&#xff1a; 直接dij堆优化 codecodecode #include<iostream> #include<cstdio> #include<queue> #define pa pair<int, int>using namespace std;int n, m, s, tot; int dis[1000100], head[1000100]; bool v[1000100];priority_queue<pa>…

在这里插入图片描述

思路:

直接dij+堆优化

c o d e code code

#include<iostream>
#include<cstdio>
#include<queue>
#define pa pair<int, int>

using namespace std;

int n, m, s, tot;
int dis[1000100], head[1000100];
bool v[1000100];

priority_queue<pa> q;

struct node
{
	int to, next, w;
}b[1000100];

void add(int x, int y, int w)
{
	b[++tot]=(node){y, head[x], w};
	head[x]=tot;
}

void dij(int x)
{
	for(int i=1; i<=n; i++)
		dis[i]=1e9;
	dis[x]=0;
	q.push(make_pair(0, x));
	while(!q.empty())
	{
		int x1=q.top().second;
		v[x1]=1;
		q.pop();
		for(int i=head[x1]; i; i=b[i].next)
		{
			int y=b[i].to;
			if(dis[y]>dis[x1]+b[i].w)
			{
				dis[y]=dis[x1]+b[i].w;
				q.push(make_pair(-dis[y], y));
			}
		}
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &s);
	for(int i=1; i<=m; i++)
	{
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		add(x, y, w);
	}
	dij(s);
	for(int i=1; i<=n; i++)
		printf("%d ", dis[i]);
	return 0;
}

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?