Dijkstra算法求最短路

P3371: 单源最短路(弱化版)https://www.luogu.com.cn/problem/P3371

P4779 单源最短路(标准版): https://www.luogu.com.cn/problem/P4779

视频详解: https://www.bilibili.com/video/BV1QESyYGE55/?spm_id_from=333.337.search-card.all.click

题目中有重边，使用邻接矩阵需加入重边判断，所以使用邻接表会更方便

struct edge {
	ll v, w;
	bool friend operator <(edge a,edge b){
		return a.w > b.w;
	} // 重载
};
priority_queue<edge> q; // 默认为大根堆，使用edge后变为小根堆

// 主函数
void dij(){
        // 堆优化
	while (!q.empty()) {
		edge tmp = q.top();
		q.pop();
		ll u = tmp.v;
		if(visited[u]) continue; // 已经是最小值了，退出
		visited[u] = 1;
		for (auto ed : a[u]) { // 遍历它指向的所有点
			int v = ed.v;
			if (!visited[v]) { // 注意需要判断能否访问!
				dis[v] = min(dis[v],tmp.w + ed.w);
				q.push({v, dis[v]});
			}
		}
	} 
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	memset(dis, 0x7f7f7f7f7f7f7f7f, sizeof(dis));

	cin >> n >> m >> s;
	dis[s]=0;// 第一个点到自己的距离为0
	for (int d1=1;d1<=m;d1++) {
		int u, v ,w;
		cin >> u >> v >> w;
		a[u].push_back({v, w});
	}
	q.push({s, 0});
	dij();
	for (int d1=1;d1<=n;d1++) {
	  if (dis[d1] > 1e15) cout << INT_MAX << " " ; //INT_MAX在climits库中
	  else cout << dis[d1] << " ";
	}
	return 0;
}