hdu2544（自己实现优先队列）

hdu2544  dij水题，用来测试自己实现优先队列对不对

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <algorithm>

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <map>

 #include <set>

 #include <string>

 #include <math.h>

 using namespace std;

 #pragma warning(disable:4996)

 typedef long long LL;

 const int INF =  << ;

 const int N =  + ;

 int len;

 struct node

 {

     int v, cost;

     int next;

 }g[+];

 int head[N], e;

 int dist[N];

 bool vis[N];

 void init(int n)

 {

     for (int i = ; i <= n; ++i)

         head[i] = -;

     e = ;

 }

 void addEdge(int u, int v, int c)

 {

     g[e].v = v;

     g[e].cost = c;

     g[e].next = head[u];

     head[u] = e++;

 }

 struct node2

 {

     int v, dist;

     bool operator<(const node2&rhs)const

     {

         return dist > rhs.dist;

     }

 }q[];

 void push(node2 tmp)//在队尾加入一个元素，只要调整到父亲结点不大于自己即可

 {

     int adjustIndex = ++len;

     for (int i = adjustIndex / ; i >= ; i /= )

     {

         if (q[i].dist < tmp.dist)

             break;

         q[adjustIndex] = q[i];

         adjustIndex = i;

     }

     q[adjustIndex] = tmp;

 }

 node2 get()

 {

     node2 ret = q[];//得到队首元素

     node2 tmp = q[len--];//将队尾元素放到队首

     int adjustIndex = ;

     //调整成一个小顶堆

     for (int i = adjustIndex * ; i <= len; i = i * )

     {

         if (i < len && q[i].dist > q[i + ].dist)

             i++;

         if (tmp.dist < q[i].dist)

             break;

         q[adjustIndex] = q[i];

         adjustIndex = i;

     }

     q[adjustIndex] = tmp;

     return ret;

 }

 void dij(int n)

 {

     //priority_queue<node2> q;

     for (int i = ; i <= n; ++i)

     {

         dist[i] = INF;

         vis[i] = false;

     }

     len = ;

     dist[] = ;

     node2 cur, tmp;

     cur.v = ;

     cur.dist = ;

     //q.push(cur);

     push(cur);

     while (len!=)

     {

         cur = get();

         //cur = q.top();

         //q.pop();

         int x = cur.v;

         if (vis[x]) continue;

         vis[x] = true;

         for (int i = head[x]; i != -; i = g[i].next)

         {

             int v = g[i].v;

             tmp.v = v;

             if (dist[v] > dist[x] + g[i].cost)

             {

                 tmp.dist = dist[v] = dist[x] + g[i].cost;

                 //q.push(tmp);

                 push(tmp);

             }

         }

     }

 }

 int main()

 {

     int n, m, a, b, c, i;

     while (scanf("%d%d", &n, &m) ,n)

     {

         init(n);

         for (i = ; i < m; ++i)

         {

             scanf("%d%d%d", &a, &b, &c);

             addEdge(a, b, c);

             addEdge(b, a, c);

         }

         dij(n);

         printf("%d\n", dist[n]);

     }

 }