ダイクストラとは、最短路がまだ固定されていない点の中から、既知の最短路の中で最も短い点を見つけて、それを固定し、この点に接続されている他の点の最短路を更新することです。最初は、始点から始点への最短路は 0 です。
それで、Dijkstraを復習して、いくつかの関数を見つけました。
make_heap (first, last, comp): 配列をヒープに変換するpush_heap (first, last, comp): 配列の末尾の数をヒープの正しい位置に浮かせるpop_heap (first, last, comp): ヒープのguiの先頭を配列の末尾に移動する
簡単にラップすると次のようになります。
void push (int x) {
heap[++hsize] = x;
std::push_heap(heap + 1, heap + 1 + hsize, cmp1);
}
void pop (void) {
std::pop_heap(heap + 1,heap + 1 + hsize--, cmp1);
}
配列を使って実装したヒープは香港の記者よりも速く、vectorを使った優先キューよりもどれだけ優れているかはわかりません。
テンプレート問題のコードは以下の通りです。
#include <cstdio>
#include <algorithm>
const int MAXM = 500000 + 5, MAXN = 100000 + 5, INF = 2147483647;
int n, m, s;
struct ed {
int to, nex, w;
} e[MAXM];
int head[MAXN], dis[MAXN], hsize;
bool v[MAXN];
int newp;
struct node {
int id, v;
} heap[MAXN];
void insert (int p1, int p2, int w) {
++newp;
e[newp].to = p2;
e[newp].w = w;
e[newp].nex = head[p1];
head[p1] = newp;
}
bool cmp1 (node x, node y) {
return x.v > y.v;
}
void push (node x) {
heap[++hsize] = x;
std::push_heap(heap + 1, heap + 1 + hsize, cmp1);
}
void pop (void) {
std::pop_heap(heap + 1,heap + 1 + hsize--, cmp1);
}
void dij (int s) {
for (int i = 1; i <= n; ++i) {
dis[i] = INF;
v[i] = 0;
}
dis[s] = 0;
hsize = 0;
push((node){s, 0});
while (hsize) {
node u = heap[1];
pop();
if (v[u.id]) continue;//固定された点
v[u.id] = 1;
for (int i = head[u.id]; i; i = e[i].nex) {
int y = e[i].to;
if (dis[y] > u.v + e[i].w) {
dis[y] = u.v + e[i].w;
push((node){y, dis[y]});
}
}
}
}
int main (void) {
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= n; ++i) {
head[i] = 0;
heap[i] = (node){0, 0};
}
for (int i = 1; i <= m; ++i) {
e[i] = (ed){0, 0, 0};
}
{
int p1, p2, w;
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &p1, &p2, &w);
insert(p1, p2, w);
}
}
dij(s);
for (int i = 1; i <= n; ++i) {
printf("%d ", dis[i]);
}
putchar('\n');
return 0;
}