使用最小堆优化Dijkstra算法

OJ5.2很简单，使用priority_queue实现了最小堆竟然都过了OJ……每次遇到relax的问题时都简单粗暴地重新push进一个节点……

然而正确的实现应该是下面这样的吧，关键在于swap堆中元素时使用pos数组存储改变位置后的编号为k的节点对应在堆中的位置。下面这种实现也很简单，d,v,p均存储在堆中，只有pos指明位置。源代码作者很聪明>_<

#include <stdio.h>#define MAXN 1200
#define MAXM 1200000
#define INF 19930317struct node
{int d, v, p;
}heap[MAXN];
int pos[MAXN], hl;int e[MAXM], cost[MAXM], next[MAXM], g[MAXN], size;int m, n, s, t;void insert(int u, int v, int w)
{e[++size] = v;next[size] = g[u];cost[size] = w;g[u] = size;
}void swap(int a, int b)
{heap[0] = heap[a];heap[a] = heap[b];heap[b] = heap[0];pos[heap[a].v] = a;pos[heap[b].v] = b;
}void heapfy()
{int i = 2;while (i <= hl){if ((i < hl) && (heap[i + 1].d < heap[i].d))i++;if (heap[i].d < heap[i >> 1].d){swap(i, i >> 1);i <<= 1;}elsebreak;}
}void decrease(int i)
{while ((i != 1) && (heap[i].d < heap[i >> 1].d)){swap(i, i >> 1);i >>= 1;}
}void relax(int u ,int v, int w)
{if (w + heap[pos[u]].d < heap[pos[v]].d){heap[pos[v]].p = u;heap[pos[v]].d = w + heap[pos[u]].d;decrease(pos[v]);}
}void delete_min()
{swap(1, hl);hl--;heapfy();
}void init()
{int u ,v ,w, i;scanf("%d%d", &m, &n);for (i = 1; i <= m; i++){scanf("%d%d%d", &u, &v, &w);insert(u, v, w);insert(v, u, w);}s = 1;t = n;
}int dijkstra()
{int u, p, i;for (i = 1; i <= n; i++){heap[i].v = pos[i] = i;heap[i].d = INF;}heap[s].p = s;heap[s].d = 0;swap(1, s);hl = n;while (hl){u = heap[1].v;delete_min();p = g[u];while (p){if (pos[e[p]] <= hl)relax(u, e[p], cost[p]);p = next[p];}}
}
int main()
{init();dijkstra();printf("%d\n", heap[pos[t]].d);return 0;
}