Dijkstra

求最短路（堆优化）

#include 
using namespace std;
#define fi first
#define se second
#define PII pair 
#define pb push_back
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m, dis[N], v[N];
vector  g[N];
int dijkstra(){
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0;
	priority_queue< PII, vector, greater > q;  //堆优化
	q.push( {0, 1} );
	while ( q.size() ){
		PII t = q.top();
		q.pop();
		int x = t.se;
		if (v[x]) continue;
		v[x] = 1;
		for (auto tt : g[x]){
			int y = tt.fi, d = tt.se;
			if (dis[y] > dis[x] + d){
				dis[y] = dis[x] + d;
				q.push( { dis[y], y} );
			}
		}
	}
	if (dis[n] == INF) return -1;
	return dis[n];
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; ++ i){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u].pb( {v, w} );
	}
	cout << dijkstra() << "\n";
	return 0;
}

Acwing 模板：https://www.acwing.com/problem/content/852/

计算最短路的数量

题目链接

http://acm.zjgsu.edu.cn/contests/117/problems/0

题目大意：

输入 \(n, m, s, e\)，分别表示点的数量、边的数量、起点和终点。点的编号从 0 开始，第二行输入每个点的快乐值（权重）。接下来 \(m\) 行每行输入三个数，\(u, v, w\)，表示从 \(u\) 到 \(v\) 有一条长为 \(w\) 的边。
输出从起点到终点的最短路的数量以及最短路的最大快乐值。

代码：

#include 
using namespace std;
#define LL long long
#define fi first
#define se second
#define PLL pair 
#define pb push_back
const int N = 1e3 + 10;
LL s, e, n, m, dis[N], v[N], w[N], cnt[N], ans[N];
vector  g[N];
void dijkstra(){
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;
	priority_queue< PLL, vector, greater > q;
	q.push( {0, s} );
	while ( q.size() ){
		PLL t = q.top();
		q.pop();
		LL x = t.se;
		if (v[x]) continue;
		v[x] = 1;
		for (auto tt : g[x]){
			LL y = tt.fi, d = tt.se;
			if (dis[y] > dis[x] + d){
				dis[y] = dis[x] + d;
				cnt[y] = cnt[x];
				ans[y] = ans[x] + w[y];
				q.push( {dis[y], y} );
			}
			else if (dis[y] == dis[x] + d){
				cnt[y] += cnt[x];
				ans[y] = max(ans[y], ans[x] + w[y]);
			}
		}
	}
}
int main(){
	cin >> n >> m >> s >> e;
	for (int i = 0; i < n; ++ i)
		scanf("%lld", &w[i]);
	for (int i = 1; i <= m; ++ i){
		LL a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);
		g[a].pb( {b, c} );
		g[b].pb( {a, c} );
	}
	cnt[s] = 1;
	ans[s] = w[s];
	dijkstra();
	cout << cnt[e] << " " << ans[e] << "\n";
	return 0;
}