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

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

 

#include 
     
      #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;        }        else            break;    }}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;}