以后慢慢看
------------
模板是HDOJ 2544
我寫的是記錄每個點在堆中的位置IncreaseKey，也可以Relax后直接往里插，用個bool數組記錄一下
-----
優化之處在于時間復雜度由n^2變為nlgn
-----
#include<cstdio>
#include<cstdlib>
int n,m;
int map[101][101],d[101];
class Heap
{
public:
int handle[101];
void Build(int n)
{
for(int i=1;i<=n;i++) a[i]=handle[i]=i;
size=n;
}
void Percup(int p)
{
int temp=a[p];
for(;d[temp]<d[a[p>>1]];p>>=1)
{
a[p]=a[p>>1];
handle[a[p]]=p;
}
a[p]=temp;
handle[a[p]]=p;
}
int DeleteMin()
{
int val=a[1];
a[1]=a[size--];
Percdown(1);
handle[val]=0;
return val;
}
bool Empty() {return size==0;}
private:
int a[101],size;
void Percdown(int p)
{
int temp=a[p],child;
for(;(p<<1)<=size;p=child)
{
child=p<<1;
if(child+1<=size && d[a[child+1]]<d[a[child]]) child++;
if(d[temp]<d[a[child]]) break;
a[p]=a[child];
handle[a[p]]=p;
}
a[p]=temp;
handle[a[p]]=p;
}
}h;
void init()
{
int i,j,c;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) map[i][j]=0x7fffffff;
d[i]=0x7fffffff;
}
d[1]=0;
while(m--)
{
scanf("%d%d%d",&i,&j,&c);
map[i][j]=map[j][i]=c;
}
}
void Relax(int num)
{
for(int i=1;i<=n;i++)
if(h.handle[i] && map[num][i]!=0x7fffffff && d[i]>d[num]+map[num][i])
{
d[i]=d[num]+map[num][i];
h.Percup(h.handle[i]);
}
}
void dijk()
{
h.Build(n);
while(!h.Empty()) Relax(h.DeleteMin());
}
int main()
{
while(scanf("%d%d",&n,&m) && n+m)
{
init();
dijk();
printf("%d\n",d[n]);
}
system("pause");
return 0;
}
---------------------
另一個版本
#include <stdio.h>
const int SIZE= 30005, MAXX=2000000000;
int n,m,tail, dist[SIZE];
bool mark[SIZE];
struct Node
{
int id, val;
Node* next;
}node[SIZE];
struct Heap{
int id, val;
}heap[2*SIZE];
void insert(int a, int b, int val)
{
Node* p = new Node;
p->id = a;
p->val = val;
p->next = node[b].next;
node[b].next = p;
}
void heappush(int id, int val)
{
heap[++tail].id = id;
heap[tail].val = val;
int child, parent, temp;
child = tail;
while((parent = child/2)>=1)
{
if(heap[child].val < heap[parent].val) // child's val < parent's val ; swap ,filter
{
temp = heap[child].id;
heap[child].id = heap[parent].id;
heap[parent].id = temp;
temp = heap[child].val;
heap[child].val = heap[parent].val;
heap[parent].val = temp;
child = parent;
}
else
break;
}
}
int heappop()
{
int child, parent, temp,ret;
ret = heap[1].id;
heap[1].id = heap[tail].id;
// swap the tail to the root
heap[1].val = heap[tail--].val;
parent = 1;
while((child=2*parent)<=tail)
{
if(child+1<=tail && heap[child+1].val < heap[child].val)
child++;
if(heap[child].val<heap[parent].val)
{
temp = heap[child].id;
heap[child].id = heap[parent].id;
heap[parent].id = temp;
temp = heap[child].val;
heap[child].val = heap[parent].val;
heap[parent].val = temp;
parent = child;
}
else
break;
}
return ret;
}
int dijkstra(int s, int t)
{
int i;
for(i=1; i<=n; i++)
{
dist[i] = MAXX;
mark[i] = false;
}
Node* p;
p = node[s].next;
while(p)
{
dist[p->id] = p->val;
heappush(p->id, p->val);
p = p->next;
}
mark[s] = true; dist[s] = 0;
for(i=1; i<n; i++)
{
int pop = heappop();
while(mark[pop])
pop = heappop();
if(pop ==t || dist[pop]==MAXX) break;
mark[pop] = true;
p = node[pop].next;
while(p)
{
if(!mark[p->id]&&
(dist[p->id]==MAXX || dist[pop]+p->val< dist[p->id]))
{
dist[p->id] = dist[pop] + p->val;
heappush(p->id, dist[p->id]);
}
p = p->next;
}
}
return dist[t];
}
int main()
{
int i,a,b,c;
scanf("%d%d", &n, &m);
for(i=1; i<=m; i++)
{
scanf("%d%d%d", &a, &b, &c);
insert(a, b, c);
}
printf("%d\n", dijkstra(n,1));
return 0;
}
posted on 2009-08-09 21:28
luis 閱讀(1815)
評論(0) 編輯 收藏 引用 所屬分類:
圖論*矩陣