自己实现优先队列

自己实现优先队列

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]);
}
}
05-11 13:55