Dijkstra算法

Dijkstra：从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。适用于单源最短路径问题

//堆优化dijsktra
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;//距离 下标 
const int N=2e5+10; 
const int inf=0x3fffffff;
int n, m, s;
int dis[N],vis[N]; 
vector<pii> g[N];
priority_queue<pii, vector<pii>, greater<pii> > q;//按照pair的第一维排序 
void dijk(){
	q.push({0, s});
	dis[s] = 0;
	while(!q.empty()){//只能用于所有边权为正数的图
		int now = q.top().second;//top一定是dis最小的点，从堆里第一个出来的是最短路 
		q.pop();
		if(vis[now]){ //有可能堆里会出现同一个now 
			continue;
		}
		vis[now] = 1;//一旦确定了某点的最短路距离，那么该点被标记为1 
		for(int  i=0;i<g[now].size();i++)
		{
			int v = g[now][i].second, w = g[now][i].first;
			if(dis[now] + w < dis[v]){
				dis[v] = dis[now] + w;
				q.push({dis[v], v});
			}
		}
	}
	return;
}
int main(){
	cin >> n >> m >> s;
	int u, v, w;
	for(int i = 0; i < m; i++){
		cin >> u >> v >> w;
		g[u].push_back({w, v});//{边权，点} 
	}
	for(int i=0;i<=n;i++)
		dis[i]=inf;
	dijk();
	for(int i = 1; i <= n; i++)
		printf("%d%c", dis[i], (i == n) ?'\n': ' ');
	return 0;
}