P1001 A+B Problem（整活-dijstra堆优化）

OK 啊，这就是普通的 a+ba+b 嘛
这是一道十分淼的题目，乍一看，这不就是dijstra堆优化的模板题吗？
首先，建立三个节点，两条线
行，OK 开始 Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
const long long N = 99999, M = 999999;
typedef pair<long long, long long> PII;
priority_queue<PII, vector<PII>, greater<PII> > q;
long long n, p, c, k, x, y, l;
long long pre[N];//链表头
long long d[N];//dis距离数组
bool f[N];//标记数组
struct Node {
	long long v, next, len;//链式前向星
} a[M * 2];
void add(long long u, long long v, long long len) {
	a[++k] = {v, pre[u], len};
	pre[u] = k;
}//建边
int dijkstra(long long h) {
	d[h] = 0;
	q.push({0, h});
	while (!q.empty()) {
		PII b = q.top();
		long long dis = b.first;
		long long pi = b.second;
		q.pop();
		if (f[pi]) continue;
		f[pi] = true;
		for (long long i = pre[pi]; i; i = a[i].next) {
			long long to = a[i].v;
			if (d[to] > dis + a[i].len) {
				d[to] = dis + a[i].len;
				q.push({d[to], to});
			}
		}
	}
	return d[3];
}//dijstra堆优化
int main() {
	//全开longlong防止数据爆掉
	cin >> x >> y; //读入x,y;
	//使用链式前向星进行建图
	add(1, 2, x);
	add(2, 3, y);
	memset(d, 0x3f, sizeof(d));
	memset(f, 0, sizeof(f));
	cout << dijkstra(1); //开始跑dijstra堆优化
	return 0;
}

时间复杂度
总共需要遍历 22 条边，插入数据修改小根堆的时间复杂度为 O(Nlog⁡2(N))O(N \log_2(N)) 所以时间复杂度为 O(3∗log⁡2(3))O(3*\log_2(3))。因为对于 稀疏图 来说边数与点数很接近，所以可以看做为 O(Nlog⁡2(N))O(N \log_2(N))。但是对于 稠密图 来说边数接近点数的平方个，如果稠密图使用堆优化版的 Dijkstra 算法，那么时间复杂度将会是 O(n2∗log⁡2(n))O(n^2*\log_2(n))，显然不如直接使用朴素 Dijkstra 算法。所以堆优化版的 Dijkstra 算法更适用于稀疏图 ，而朴素 Dijkstra 算法更适用于稠密图。
综上所述：本程序的时间复杂度为 O(3∗log2(3))O(3*log_2(3))
最后祝大家早日成为大牛