【最短路】【Dij】单源最短路径

链接

单源最短路径

题目描述

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

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

样例输入

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

样例输出

0 2 4 3

思路

其实就是个普通的最短路
但是题库很“良心”地构造了数据
spfa会被卡掉，所以用dij
顺手加了个堆优化

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>

using namespace std;

priority_queue<pair<int , int> > Q;

struct node
{
	int to, next, val;
}g[200005];

int n, t, m, s;
int dis[100005], vis[100005], h[100005];

void add(int x, int y, int z)
{
	g[++t] = (node){y, h[x], z}; h[x] = t;
}//连边

void dij(int s)
{
	memset(dis, 0x7f, sizeof(dis));
	dis[s] = 0;
	Q.push(make_pair(0, s));
	while(Q.size())
	{
		int tot = Q.top().second;
		Q.pop();
		if(vis[tot]) continue;
		vis[tot] = 1;
		for(int i = h[tot]; i; i = g[i].next)
		{
			int to = g[i].to;
			if(dis[to] > dis[tot] + g[i].val && !vis[to])
				dis[to] = dis[tot] + g[i].val,
				Q.push(make_pair(-dis[to], to));
		}
	}
}//Dij + 堆优化

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