Background :
我先描述一下这个问题吧（就在之前的星期还和 doc 讨论过呢），就是如何用STL优美的写出加堆优化的 dijktra … 遇到的困难主要是无法得到结点在堆中的位置…. （除非可以有办法写到 STL 里面去。。多加一点东西，但这亦是一件困难之事呀。，我们的想法是如果要遇到这种情况时必须手写堆。（或者我们写一些 Spfa 替代一下也不错。）
加堆的Dijkstra 是我高二暑假的时候自己研究出来的（这花了我很久的一段时间），所以印象很深，而且我也想借此机会比较一下不同的写法。
今天上午写 Astar 的时候 ，我找到了解决这个问题的一种方法。（( ⊙ o ⊙ )o… ＃—＊@—（＊）
…
Archieve :
Problem: Rqnoj 341 星门跳跃
#include <iostream>
#include <vector>
using namespace std;
const int INF = 100000;
const int N = 30001;
struct edge{
int p, w;
};
vector<edge> adj[N];
int Q[N], H[N], P[N]; int size;
int n, m;
void exchange(int a, int b){
swap(Q[a], Q[b]); swap(H[a], H[b]);
P[H[a]] = a; P[H[b]] = b;
}
void down(int x){
int l, r, k;
while (true){
l = x << 1; r = l + 1;
if (l<=size&&Q[l]<Q[x]) k = l; else k = x;
if (r<=size&&Q[r]<Q[k]) k = r;
if (x==k) return;
exchange(x, k);
x = k;
}
}
void up(int x){
int y = x >> 1;
while (y>0&&Q[x]<Q[y]){
exchange(x, y);
x = y; y >>= 1;
}
}
int extract(){
exchange(1, size--); down(1);
return(H[size+1]);
}
void decrease(int x, int k){
Q[x] = k; up(x);
}
void init(){
cin >> n >> m;
int a, b; edge x;
for (int i=0;i<m;i++){
cin >> a >> b >> x.w;
x.p = b; adj[a].push_back(x);
x.p = a; adj[b].push_back(x);
}
}
void dijkstra(){
for (int i=1;i<=n;i++){
P[i] = H[i] = i;
Q[i] = INF;
}
size = n, Q[1] = 0;
int u, v;
for (int i=0;i<n;i++){
u = extract();
if (u == n) return;
for (vector<edge>::iterator it=adj[u].begin();it!=adj[u].end();it++){
v = (*it).p;
if (P[v]<=size&&Q[P[u]] + (*it).w < Q[P[v]])
decrease(P[v], Q[P[u]] + (*it).w);
}
}
}
int main(){
init(); dijkstra();
cout << Q[P[n]] << endl;
}
#include <iostream>
#include <vector>
using namespace std;
const int INF = 100000;
const int N = 30001;
struct edge{
int p, w;
};
vector<edge> adj[N];
int Q[N], D[N], P[N];
int size;
int n, m;
void exchange(int a, int b){
swap(Q[a], Q[b]);
P[Q[a]] = a; P[Q[b]] = b;
}
void down(int x){
int l, r, k;
while (true){
l = x << 1; r = l + 1;
if (l<=size&&D[Q[l]]<D[Q[x]]) k = l; else k = x;
if (r<=size&&D[Q[r]]<D[Q[k]]) k = r;
if (x==k) return;
exchange(x, k);
x = k;
}
}
void up(int x){
int y = x >> 1;
while (y>0&&D[Q[x]]<D[Q[y]]){
exchange(x, y);
x = y; y >>= 1;
}
}
int extract(){
exchange(1, size--); down(1);
return(Q[size+1]);
}
void decrease(int x, int k){
D[x] = k; up(P[x]);
}
void init(){
cin >> n >> m;
int a, b; edge x;
for (int i=0;i<m;i++){
cin >> a >> b >> x.w;
x.p = b; adj[a].push_back(x);
x.p = a; adj[b].push_back(x);
}
}
void dijkstra(){
for (int i=1;i<=n;i++){
Q[i] = P[i] = i; D[i] = INF;
}
size = n, D[1] = 0;
int u, v;
for (int i=0;i<n;i++){
u = extract();
if (u == n) return;
for (vector<edge>::iterator it=adj[u].begin();it!=adj[u].end();it++){
v = (*it).p;
if (P[v]<=size&&D[u] + (*it).w < D[v])
decrease(v, D[u] + (*it).w);
}
}
}
int main(){
init(); dijkstra();
cout << D[n] << endl;
}
Handle 数组 记录堆中的元素对应哪个结点。
Pos 数组 维护每个结点在堆中的位置。
这两个是一组互逆操作… 也就是
Handle[Pos[i]] = Pos[Handle[i]] = i;
Queue 数组记录堆中元素的关键字，也就是到源点的 Dist， 最短路径估计。
1.
代码一 中 void exchange() 的位置
P[H[a]] = a; P[H[b]] = b;
是从
swap(P[H[a]], P[H[b]]);
换写的.
这样写可以少一个语句不过会根据H数组有没有交换而有影响。
比如如果放前面的话会要写成这样。
P[H[a]] = b; P[H[b]] = a;
2.
经过观察，我们发现 Handle 元素和 Key 元素同时属于堆中的一个结点，这样可以把他们打包成一个 Struct ，交换的时候同时进行。
但是 Pos 数组就不行了，事实上我们发现问题就出在 Pos 数组上….
因为在使用 STL:Priority_queue 的时候，没有办法往里面改写 void exchange()，也就不能即时的维护 Pos 数组了。
我们希望可以以某种方式避免 Pos 数组的出现，因此我们尝试了代码II。
3.
但是我们很快发现代码二只是将关键字保存在了堆外。。并未能完成之前的要求。。。看起来问题变得非常棘手，因为松弛操作里必须要用对哦啊，似乎没有办法不写 Pos 数组。。。
除非，
1. 如果题目不完全要求死用邻接表存储，那样用邻接矩阵做O(1)的测试的话，可以直接扫描堆。（因为可以容易的得到 Handle 数组。）
但是这样就没有用了。
2. 对取出一个，松弛完所有结点后，在一起维护堆。。。
（我还不能确定这个方法有多大的可行。。。但是感觉和上面那种一样，都不适合处理稀疏图）
。
。。。
但是下面确实存在一种，简洁的方法解决这个问题。
通过允许堆中一个点存在多次，做延迟认可。（额，用空间换取编程复杂度。。。）
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1000000;
const int N = 30001;
struct edge{
int p, w;
};
vector<edge> adj[N];
int D[N]; bool C[N];
int n, m;
struct comp{
bool operator()(int a, int b){
return (D[a]>D[b]);
}
};
priority_queue< int, vector<int>, comp > Q;
void init(){
cin >> n >> m;
int a, b; edge x;
for (int i=0;i<m;i++){
cin >> a >> b >> x.w;
x.p = b; adj[a].push_back(x);
x.p = a; adj[b].push_back(x);
}
}
void dijkstra(){
for (int i=1;i<=n;i++){
D[i] = INF; C[i] = true;
}
while (!Q.empty()) Q.pop();
Q.push(1);
D[1] = 0;
int u, v;
for (int i=0;i<n;i++){
while (!Q.empty()){
u = Q.top(), Q.pop();
if (C[u]) break;
}
if (!C[u]||u==n) return;
C[u] = false;
for (vector<edge>::iterator it=adj[u].begin();it!=adj[u].end();it++){
v = (*it).p;
if (C[v]&&D[u] + (*it).w < D[v]){
D[v] = D[u] + (*it).w;
Q.push(v);
}
}
}
}
int main(){
init(); dijkstra();
cout << D[n] << endl;
}
