Dijkstra算法的核心：選出一個已經求出最短路的點，加上一條邊求出另一個點的最短路；d'[v]=min{d[u]+w(u,v)|u的最短距離已求出且邊（u,v)存在} 借助堆取出d[u];
http://acm.hdu.edu.cn/showproblem.php?pid=2544
堆+鄰接表
花了一上午。。。
#include<iostream>
using namespace std;
#define N 110
#define inf 0x7fffffff
typedef struct node
{
int adj;
struct node * next;
int w;
}node,*pnode;
node adjlist[N];
typedef struct Heap
{
int x;
int dis;
}Heap;
Heap heap[1000];
bool hash[N];
int len,d[N],n,m;
void insert(Heap in)
{
int u=++len;
while(u>1&&heap[u>>1].dis>in.dis)
{
heap[u]=heap[u>>1];
u>>=1;
}
heap[u]=in;
}
Heap pop()
{
Heap first=heap[1],last=heap[len--];
int u=1,v;
while(2*u<=len)
{
v=u<<1;
if(v+1<=len&&heap[v+1].dis<heap[v].dis)
v++;
if(heap[v].dis<last.dis)
heap[u]=heap[v];
else
break;
u=v;
}
heap[u]=last;
return first;
}
void insert_adjlist(int a,int b, int c)
{
pnode p,q;
p=&adjlist[a];
while(p->next!=NULL)
p=p->next;
q=new node;
q->adj=b;
q->next=NULL;
q->w=c;
p->next=q;
}
int bfs()
{
Heap min,in;
pnode p;
in.x=1;
in.dis=0;
d[1]=0;
insert(in);
while(len)
{
min=pop();
if(min.x==n)
return min.dis;
if(hash[min.x])
continue;
hash[min.x]=true;
p=adjlist[min.x].next;
while(p!=NULL)
{
if(!hash[p->adj])
{
in.x=p->adj;
in.dis=min.dis+p->w;
if(in.dis<d[in.x])
{
d[in.x]=in.dis;
insert(in);
}
}
p=p->next;
}
}
return -1;
}
int main()
{
int i,a,b,c,min;
while(scanf("%d%d",&n,&m),n+m)
{
for(i=1,len=0;i<=n;i++)
{
adjlist[i].next=NULL;
hash[i]=false;
d[i]=inf;
}
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
insert_adjlist(a,b,c);
insert_adjlist(b,a,c);
}
min=bfs();
printf("%d\n",min);
}
}
優先隊列+鄰接表
#include<iostream>
#include<queue>
using namespace std;
#define N 110
#define inf 0x7fffffff
typedef struct node{
int adj;
struct node * next;
int w;
}node,*pnode;
node adjlist[N];
typedef struct Heap
{
bool operator <(Heap T)const
{
return T.dis<dis;
}
int x;
int dis;
}Heap;
priority_queue<Heap>Q;
bool hash[N];
int len,d[N],n,m;
void insert_adjlist(int a,int b, int c)
{
pnode p,q;
p=&adjlist[a];
while(p->next!=NULL)
p=p->next;
q=new node;
q->adj=b;
q->next=NULL;
q->w=c;
p->next=q;
}
int bfs()
{
Heap min,in;
pnode p;
while(!Q.empty())
Q.pop();
in.x=1;
in.dis=0;
d[1]=0;
Q.push(in);
while(!Q.empty())
{
min=Q.top();
Q.pop();
if(min.x==n)
return min.dis;
if(hash[min.x])
continue;
hash[min.x]=true;
p=adjlist[min.x].next;
while(p!=NULL)
{
if(!hash[p->adj])
{
in.x=p->adj;
in.dis=min.dis+p->w;
if(in.dis<d[in.x])
{
d[in.x]=in.dis;
Q.push(in);
}
}
p=p->next;
}
}
return -1;
}
int main()
{
int i,a,b,c,min;
//freopen("123.out","w",stdout);
while(scanf("%d%d",&n,&m),n+m)
{
for(i=1,len=0;i<=n;i++)
{
adjlist[i].next=NULL;
hash[i]=false;
d[i]=inf;
}
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
insert_adjlist(a,b,c);
insert_adjlist(b,a,c);
}
min=bfs();
printf("%d\n",min);
}
return 0;
}
普通的Dijkstra
#include<stdio.h>
#define min(a,b) a>b?b:a
#define inf 0x7FFFFFFF
int map[101][101];
int minload[101];
int visit[101];
int main()
{
int start,next,i,j,min,x,y,dis,n,m;
while(scanf("%d%d",&n,&m),m||n)
{
for(i=1;i<=n;i++)
{
minload[i]=inf;
visit[i]=0;
for(j=1;j<=n;j++)
map[i][j]=inf;
}
while(m--)
{
scanf("%d%d%d",&x,&y,&dis);
map[x][y]=map[y][x]=dis;
}
start=1;
visit[1]=1;
minload[start]=0;
while(start!=n)
{
min=inf;
for(i=1;i<=n;i++)
{
if(map[start][i]!=inf)
minload[i]=min(minload[i],minload[start]+map[start][i]);
if(!visit[i]&&minload[i]<min)
{
next=i;
min=minload[i];
}
}
visit[next]=1;
start=next;
}
printf("%d\n",minload[n]);
}
}
折騰了半天，感覺如果是比賽的話還是選擇最后一種模板，編程復雜度低點（假設題目條件不是那么苛刻
）
posted on 2009-11-26 14:48
西風蕭瑟 閱讀(4882)
評論(3) 編輯 收藏 引用 所屬分類:
圖論