某岛

… : "…アッカリ～ン . .. . " .. .
August 7, 2010

不维护pos数组的情况下优美的写出 STL:Dijkstra …

Archieve :

Problem: Rqnoj 341 星门跳跃

```#include <iostream>
#include <vector>
using namespace std;
const int INF = 100000;
const int N = 30001;
struct edge{
int p, w;
};

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;
}
}
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;
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;
};

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;
}
}
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;
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.

P[H[a]] = a; P[H[b]] = b;

swap(P[H[a]], P[H[b]]);

P[H[a]] = b; P[H[b]] = a;

2.

3.

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;
};
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;
}
}
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;