http://acm.hdu.edu.cn/showproblem.php?pid=2544
#include<stdio.h>
#define Max 1000001
#include<string>
struct Road{
int dis;
int to;
struct Road * next;
};
Road map[1000001],*tail[1000001];
struct Heap{
int x,dis;
}hh[1000001];
bool hash[1000001];
int n,m;
int len;
void PutHeap(Heap a)
{
int i;
for(i=++len;hh[i>>1].dis > a.dis;i>>=1)
hh[i] = hh[i>>1];
hh[i] = a;
}
Heap GetHeap()
{
Heap min = hh[1];
Heap last = hh[len--];
int i,s;
for(i=1;2*i<=len;i=s)
{
s = i<<1;
if(s+1<=len && hh[s+1].dis < hh[s].dis)
s ++;
if(hh[s].dis < last.dis)
hh[i] = hh[s];
else
break;
}
hh[i] = last;
return min;
}
int bfs()
{
Heap a;
a.x = 1;
a.dis = 0;
PutHeap(a);
while(len)
{
Heap min = GetHeap();
if(min.x == n)
return min.dis;
int x = min.x;
if(!hash[x])
continue;
hash[x] = false;
int dis = min.dis;
Road *p;
p = map[x].next;
while(p!=NULL)
{
int b = p->to;
if(hash[b])
{
a.x = b;
a.dis = p->dis + dis;
PutHeap(a);
}
p = p->next;
}
}
}
int main()
{
while(scanf("%d%d",&n,&m),n+m)
{
len = 0;
for(int i=1;i<=n;i++)
{
hash[i] = true;
map[i].next = NULL;
tail[i] = &map[i];
}
for(i=0;i<m;i++)
{
int a,b,dis;
Road *p,*q;
p = (Road *)malloc(12);
q = (Road *)malloc(12);
scanf("%d%d%d",&a,&b,&dis);
p->next = NULL;
p->dis = dis;
p->to = b;
tail[a]->next = p;
tail[a] = tail[a]->next;
q->next = NULL;
q->dis = dis;
q->to = a;
tail[b]->next = q;
tail[b] = tail[b]->next;;
}
printf("%d\n",bfs());
}
return 0;
}
posted on 2009-03-27 18:18
shǎ崽 阅读(460)
评论(0) 编辑 收藏 引用