hdu2544（自己实现优先队列）-白红宇

hdu2544（自己实现优先队列）

阅读量：4970 次

发布时间：2019-06-12

本文共 2480 字，大约阅读时间需要 8 分钟。

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

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
               10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 using namespace std; 14 #pragma warning(disable:4996) 15 typedef long long LL; 16 const int INF = 1 << 30; 17 const int N = 1000 + 10; 18 int len; 19 struct node 20 { 21 int v, cost; 22 int next; 23 }g[10000+10]; 24 int head[N], e; 25 int dist[N]; 26 bool vis[N]; 27 void init(int n) 28 { 29 for (int i = 1; i <= n; ++i) 30 head[i] = -1; 31 e = 0; 32 } 33 void addEdge(int u, int v, int c) 34 { 35 g[e].v = v; 36 g[e].cost = c; 37 g[e].next = head[u]; 38 head[u] = e++; 39 } 40 struct node2 41 { 42 int v, dist; 43 bool operator<(const node2&rhs)const 44 { 45 return dist > rhs.dist; 46 } 47 }q[100000]; 48 49 50 void push(node2 tmp)//在队尾加入一个元素，只要调整到父亲结点不大于自己即可 51 { 52 int adjustIndex = ++len; 53 for (int i = adjustIndex / 2; i >= 1; i /= 2) 54 { 55 if (q[i].dist < tmp.dist) 56 break; 57 q[adjustIndex] = q[i]; 58 adjustIndex = i; 59 } 60 q[adjustIndex] = tmp; 61 } 62 63 node2 get() 64 { 65 node2 ret = q[1];//得到队首元素 66 node2 tmp = q[len--];//将队尾元素放到队首 67 int adjustIndex = 1; 68 //调整成一个小顶堆 69 for (int i = adjustIndex * 2; i <= len; i = i * 2) 70 { 71 if (i < len && q[i].dist > q[i + 1].dist) 72 i++; 73 if (tmp.dist < q[i].dist) 74 break; 75 q[adjustIndex] = q[i]; 76 adjustIndex = i; 77 } 78 q[adjustIndex] = tmp; 79 return ret; 80 } 81 82 void dij(int n) 83 { 84 //priority_queue
                  
                    q; 85 for (int i = 1; i <= n; ++i) 86 { 87 dist[i] = INF; 88 vis[i] = false; 89 } 90 len = 0; 91 dist[1] = 0; 92 node2 cur, tmp; 93 cur.v = 1; 94 cur.dist = 0; 95 //q.push(cur); 96 push(cur); 97 while (len!=0) 98 { 99 cur = get();100 //cur = q.top();101 //q.pop();102 int x = cur.v;103 if (vis[x]) continue;104 vis[x] = true;105 for (int i = head[x]; i != -1; i = g[i].next)106 {107 int v = g[i].v;108 tmp.v = v;109 if (dist[v] > dist[x] + g[i].cost)110 {111 tmp.dist = dist[v] = dist[x] + g[i].cost;112 //q.push(tmp);113 push(tmp);114 }115 }116 117 }118 }119 int main()120 {121 int n, m, a, b, c, i;122 while (scanf("%d%d", &n, &m) ,n)123 {124 init(n);125 for (i = 0; i < m; ++i)126 {127 scanf("%d%d%d", &a, &b, &c);128 addEdge(a, b, c);129 addEdge(b, a, c);130 }131 dij(n);132 printf("%d\n", dist[n]);133 }134 }