#include<iostream>
#include<cstdio>
using namespace std;
int n,m,u,v,w,q;
int head[10001],next[200001],data[200001],value[200001];
int heap[10001],dis[10001];
void update(){
int x,y;
x=heap[1];
y=head[x];
while (y!=0){
dis[data[y]]=min(dis[x]+value[y],dis[data[y]]);
y=next[y];
}
}
void adjust(int x){
int p,minDis;
p=x;
minDis=dis[heap[x]];
if (x*2<=n)
if (dis[heap[x*2]]<minDis){
p=x*2;
minDis=dis[heap[x*2]];
}
if (x*2+1<=n)
if (dis[heap[x*2+1]]<minDis){
p=x*2+1;
minDis=dis[heap[x*2+1]];
}
if (p!=x){
swap(heap[x],heap[p]);
adjust(p);
}
}
void dijkstra(int x){
int i,s=n;
for (i=1;i<=n;i++)
heap[i]=i;
dis[1]=0;
for (i=2;i<=n;i++)
dis[i]=1111111111;
while (s>0){
update();
swap(heap[1],heap[s]);
s--;
for (i=s/2;i>=1;i--)
adjust(i);
}
}
int main(){
int i,j;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
next[i*2-1]=head[u],data[i*2-1]=v,value[i*2-1]=w,head[u]=i*2-1;
next[i*2]=head[v],data[i*2]=u,value[i*2]=w,head[v]=i*2;
}
dijkstra(1);
return 0;
}
Dijkstra+堆优化
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 我的配置：4台服务器组成的Elasticsearch集群，每台服务器只作为一个节点。其中有两台数据节点一台客户端节...
