学习笔记_ 关于堆优化的dijk... [我好傻啊...]

经济基础决定上层建筑

菜鸡的 新认知

细节上的差异还是很考验理解呢… 我还是太菜了… noip2017的划水似乎能预见了呢…
dijk的堆优化毕竟只是堆优化呢… 在DYYZ没学BF就学SPFA怕是一个很大的失误吧… 学优化前还是应该掌握好本体啊…
仅仅从优化的角度来看dijk的代码就好理解了呢… 优先队列的作用仅仅是找到 d 最小的一个点… v 数组的改变完全没有变呢…
SPFA是更新后就把当前的点入队…所以在队列里这个数组在入队后就设为true了…
而dijk是确定当前的点是最短路最小的时候才把v设成true
看来我还是菜啊… 今年爆零也不会太出乎意料吧… 顺理成章啊…

沙茶的 代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
struct edg
{
int from;
int to;
int cost;
int next;
};
struct node
{
int d;
int bh;
};
struct cmp
{
bool operator () (node a, node b)
{
return a.d > b.d;
}
};
struct dijk
{
int n;
int m;

bool v[MAXN];

edg b[MAXM];
int g[MAXN];
int cntb;

node a[MAXN];
int s, t;

void init()
{
memset(g, 0, sizeof(g));
cntb = 0;
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= n; i++)
a[i].bh = i;
int srx, sry, srz;
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &srx, &sry, &srz);
ade(srx, sry, srz);
}
}

void ade(int fr, int to, int co)// add an edge
{
b[++cntb].from = fr;
b[cntb].to = to;
b[cntb].cost = co;
b[cntb].next = g[fr];
g[fr] = cntb;
}

void DD()// Emmmm...
{
priority_queue<node, vector <node>, cmp> q;
memset(v, false, sizeof(v));
for (int i = 1; i <= n; i++)
{
a[i].d = INF;
}
a[s].d = 0;
q.push(a[s]);
node dq;
while(!q.empty())
{
dq = q.top(); q.pop();
if (v[dq.bh])
continue;
v[dq.bh] = true;
for (int j = g[dq.bh]; j; j = b[j].next)
{
if (a[b[j].to].d > dq.d + b[j].cost)
{
a[b[j].to].d = dq.d + b[j].cost;
q.push(a[b[j].to]);
}
}
}
}
}

By 被吓哭的 Cansult