Dijkstra算法

单源最短路算法，不能处理负环，朴素版时间复杂度\(O(n^2)\)，堆优化版时间复杂度\(O(nlogn)\)。
Dijkstra算法的流程是：
将所有的节点分为A、B的两个集合，一开始A集合中只有起点，其他的节点在B集合。定义B中的节点与A的距离：若邻接A中的结点，则距离为边权；反之距离无穷大。
1.找到与A距离最小的B集合中的节点，称之为d。（朴素版需要遍历B集合，堆优化版直接得到）
2.将d加入集合A，并在集合B中删去d。
3.更新B到A的距离。（只需更新d在B中的邻接节点）
4.若B集合为空，则退出；反之回到步骤1。
模板题目练习：洛谷：P4779

代码示例：（用优先队列实现的堆优化版）

#include <bits/stdc++.h>

const int maxN = 100005, maxM = 500005;

struct edge
{
	int to, dis, next;
};
edge eg[maxM];

int head[maxN], dis[maxN], cnt;
bool vis[maxN];
int n, m, s;

inline void add_edge(int u, int v, int d)
{
	cnt++;
	eg[cnt].dis = d;
	eg[cnt].to = v;
	eg[cnt].next = head[u];
	head[u] = cnt;
}

struct node
{
	int dis;
	int pos;
	bool operator<(const node& x) const
	{
		return x.dis < dis;
	}
};

std::priority_queue<node> nd;

void dijkstra()
{
	dis[s] = 0;
	nd.push(node({ 0, s }));
	while (!nd.empty())
	{
		node tmp = nd.top();
		nd.pop();
		int x = tmp.pos, d = tmp.dis;
		if (vis[x])
			continue;
		vis[x] = true;
		for (int i = head[x]; i; i = eg[i].next)
		{
			int y = eg[i].to;
			if (dis[y] > dis[x] + eg[i].dis)
			{
				dis[y] = dis[x] + eg[i].dis;
				if (!vis[y])
				{
					nd.push(node({ dis[y], y }));
				}
			}
		}
	}
}