[算法应用]dijkstra算法的应用

先看一眼原始dijkstra算法，参考自dijkstra算法C++实现_c++实现djikstra-CSDN博客

分为三步

1. 找到当前最优的
2. 把当前最优的，不参与后面的更新
3. 逐个比较是否更新

dijkstra算法的应用

题目大概是要从图上找一条权值不减的路径，且要经过最多的点。

所以用 Dijsktra 更新的原则是，1到该点的经过的点更多，则更新。

使用优先队列自动排序，排序的原则是：

1. 首先，如果这两个点的权值，a>b，那么在优先级里，a<b（解释：要选权值更小的点，因为权值更大的话，就不是不减了）
2. 接着，如果两点权值相等，就让1到该点经过的点更多的那个点优先（解释：我们的目的就是找点最多的那条路）

附上大佬的代码

struct T {
	int fi, se;
	friend bool operator < (T x, T y) {
		if (a[x.se] == a[y.se]) {
			if (x.fi == y.fi) return x.se > y.se;
			else return x.fi < y.fi;
		}
		else return a[x.se] > a[y.se];
	}
};
void dijkstra() {
	priority_queue<T> que;
	que.push({1, 1}); d[1] = 1;
	while (que.size()) {
		T p = que.top(); que.pop();
		int u = p.se, w = p.fi;
		if (st[u]) continue;
		st[u] = true;
		for (auto v : e[u]) {
			if (a[v] < a[u]) continue;
			int nw = d[u] + (a[v] != a[u]);
			if (nw > d[v]) {
				d[v] = nw;
				que.push({d[v], v});
			}
		}
	}
	cout << d[n] << "\n";
}