单源最短路模板（dij + 优先队列）

为什么要用dij：

很多人也许学了spfa，觉得简单方便，然而呢，spfa的复杂度是O(玄学)，容易被出题人出数据卡，于是我们要学用优先队列优化的dij。

简介：

如果大家理解dij算法的核心，那么也会很容易理解为什么优先队列可以优化的。
没优化前的dij，我们每次松弛都要遍历 $1\to n$1→n，来找到 $dis\left[i\right]$dis[i]最小的点，而总共要松弛 $n-1$n−1次，复杂度是 $O\left(n^2\right)$O(n2)。
用优先队列，相当于把遍历的过程省去了，队首就是当前dis[i] $(1\le i\le n)$(1≤i≤n)最小的点 $a$a，把复杂度降到了 $O\left(lo{g}_{2}N\right)$O(log2​N)
值得一提的是，dij算法只能用于非负权图

代码如下：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
#define N 200005
#define inf 2147483647
using namespace std;
struct node{
	int a, b, c, n;
	bool operator < (const node & A) const{
		return c > A.c;
	}
}d[N], e;
int h[N], dis[N], cnt;
priority_queue<node> q;
void cr(int a, int b, int c){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
int main(){
	int i, j, n, m, a, b, c, s;
	scanf("%d%d%d", &n, &m, &s);
	for(i = 1; i <= m; i++){
		scanf("%d%d%d", &a, &b, &c);
		cr(a, b, c);
	}
	for(i = 1; i <= n; i++) dis[i] = inf;
	dis[s] = 0;
	e.a = s, e.c = 0;
	q.push(e);
	while(!q.empty()){
		e = q.top(); q.pop();
		a = e.a;
		if(e.c != dis[a]) continue;
		for(i = h[a]; i; i = d[i].n){
			b = d[i].b;
			c = d[i].c;
			if(dis[b] > dis[a] + c){
				dis[b] = dis[a] + c;
				e.a = b; e.c = dis[b];
				q.push(e);
			}
		}
	}
	for(i = 1; i <= n; i++) printf("%d ", dis[i]);
	return 0;
}