Dijkstra は、最短経路が確定していない点から既知の最短経路が最も短い点を見つけ、それを確定させ、その点に接続された他の点の最短経路を更新することを繰り返すアルゴリズムです。最初に、ソース点からソース点への最短経路は 0 です。
したがって、Dijkstraを復習していくうちに、いくつかの関数を見つけました。
make_heap (first, last, comp): 配列をヒープに変換します。push_heap (first, last, comp): 配列の末尾の要素を適切な位置に浮かび上がらせます。pop_heap (first, last, comp): ヒープの先頭要素を配列の末尾に移動します。それでは、簡単にラップしてみましょう。
配列を使用して実装されたヒープは、香港の記者よりも速く動作します。ベクターを使用した優先キューの実装よりも高速です。
テンプレート問題のコードは以下の通りです。
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);
}
#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;
}