Dijkstra 嘛，就是每次從最短路徑未固定的點中找到已知最短路徑最短的點，然後將它固定，並更新這個點連接的其他點的最短路徑。最開始時，源點到源點的最短路徑為 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;
}