单源最短路径

题目描述

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

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

输入格式

第一行为三个正整数n,m,s。 第二行起 m 行，每行三个非负整数 ui​,vi​,wi​，表示从 ui​ 到 vi​ 有一条权值为 wi​ 的有向边。

输出格式

输出一行 n 个空格分隔的非负整数，表示 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

这就是一道图。

但是用邻接矩阵太浪费空间了，还是用邻接表好一点，邻接表，用的是动态数组，这样会节省空间。

这里定义一个结构体node，里面两个int元素，to和dis，to是到达的节点，dis表示路径长度，让后建立动态数组a，数据类型设为node，输入时的存储就像这样：

a[u].push_back(node{v,w});

然后就是写搜索函数，这道题使用的算法是dijkstra

用在这道题上面，那就把点分为两种，蓝点和白点，蓝点就是没有确定最小值的，而白点就是已经确定了的，从s开始找他通往的所有蓝点y，用数组dis记录到达y点的长度，接着，再从剩下的蓝点中，找一个值最小的，标记为白点，以他为基础，查找与之相连的蓝点，如此循环

然后要注意，记录dis记录的同时，如果元素没被访问，就进行入队操作。

最后输出dis数组的值就行了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,s;
struct node{
	int to,dis;
	friend bool operator <(node a,node b){
		return a.dis>b.dis;
	}
};
priority_queue<node>q;
vector<node>a[N];
int dis[N];
int vis[N];
void dij(){
	for(int i=1;i<=n;i++)dis[i]=INT_MAX;
	dis[s]=0;
	q.push(node{s,0});
	while(!q.empty()){
		node t=q.top();
		q.pop();
		int x=t.to;
		if(vis[x]==1)continue;
		vis[x]=1;
		for(int i=0;i<a[x].size();i++){
			int y=a[x][i].to;
			int z=a[x][i].dis;
			dis[y]=min(dis[y],dis[x]+z);
			if(vis[y]==0)q.push(node{y,dis[y]});
		}
	}
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&s);
	int u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		a[u].push_back(node{v,w});
	}
	dij();
	for(int i=1;i<=n;i++)printf("%lld ",dis[i]);
}