简洁点的：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10005, M = 200005, oo = 0x3fffffff;
struct DistT{
int v,w;
bool operator < (const DistT &x)const{
return w>x.w||w==x.w&&v>x.v;
}
};
struct EdgeT{ int to,w,next; };
EdgeT edge[M];
DistT dist[M];
bool ok[N];
int n,m,en=0,head[N],d[N];
void insert(int a,int b,int c){
edge[en].to = b;
edge[en].w = c;
edge[en].next = head[a];
head[a] = en++;
}
void init(){
fill(head,head+N,-1);
fill(d,d+N,oo);
cin>>n>>m;
for (int i=0,a,b,c;i<m;i++){
cin>>a>>b>>c;
insert(a,b,c);
}
}
void dijkstra(int source){
int k=0;
for (int j=head[source];j!=-1;j=edge[j].next)
dist[k].v=edge[j].to,dist[k++].w = edge[j].w,
d[edge[j].to] = edge[j].w;
ok[source]=true; d[source]=0;
make_heap(dist,dist+k);
for (int i=1;i<n;i++){
//d[dist[0].v]=dist[0].w;
int p=dist[0].v;
pop_heap(dist,dist+k); k--;
if (ok[p]) { i--; continue; }
ok[p]=true;
for (int j=head[p];j!=-1;j=edge[j].next)
if (!ok[edge[j].to]&&d[p]+edge[j].w<d[edge[j].to]){
d[edge[j].to]=d[p]+edge[j].w;
dist[k].v=edge[j].to;
dist[k].w=d[edge[j].to];
++k;
push_heap(dist,dist+k);
}
}
}
int main()
{
init();
dijkstra(1);
for (int i=1;i<=n;i++) cout<<d[i]<<" "; cout<<endl;
return 0;
}
/*测试数据
5 7
1 2 10
1 4 30
2 3 50
4 3 20
4 5 60
1 5 100
3 5 10
输出：
0 10 50 30 60
*/ 代码：
//堆优化的dijsktra 单源点最短路径
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100005, M = 200005, oo=0x7fffffff;
struct EdgeT{
int to,wei;
int next;
}edge[M];
int n,e=0,head[N],dist[N],a[N],b[N];
bool ok[N]={false};
void AddEdge(int x,int y,int z){
edge[e].to=y;
edge[e].wei=z;
edge[e].next=head[x];
head[x]=e++;
}
void init(){
int en;
cin>>n>>en;
fill(head,head+N,-1);
for (int i=0,a,b,c;i<en;i++){
cin>>a>>b>>c;
AddEdge(a,b,c);
}
}
void jiaohuan(int &x,int &y){
swap(x,y);
swap(b[x],b[y]);
}
void siftdown(int root,int m){
int child=root*2+1;
while (child<=m){
if (child<m&&dist[a[child+1]]<dist[a[child]]) child++;
if (dist[a[child]]<dist[a[root]]){
jiaohuan(a[child],a[root]);
root=child;
child=root*2+1;
}
else break;
}
}
void siftup(int child){
int parent=(child-1)/2;
while (child){
if (dist[a[child]]<dist[a[parent]]){
jiaohuan(a[child],a[parent]);
child=parent;
parent=(child-1)/2;
}
else break;
}
}
void shortestpath(int source){
fill(dist+1,dist+n+1,oo);
dist[source]=0;
for (int i=head[source];i!=-1;i=edge[i].next)
dist[edge[i].to]=edge[i].wei; //用源点到各顶点直达距离初始化dist数组
ok[source]=true;
for (int i=0;i<n;i++) a[i]=i+1;
swap(a[source-1],a[n-1]);
for (int i=(n-2-1)/2;i>=0;i--) siftdown(i,n-2); //make_heap(a,a+n-1,comp);
for (int i=0;i<n-1;i++) b[a[i]]=i;
for (int i=n-2;i>=1;i--){
int k=a[0];
ok[k]=true; //到顶点k的最短路径已求出，置标记
jiaohuan(a[0],a[i]);
siftdown(0,i-1);
for (int j=head[k];j!=-1;j=edge[j].next){
if (!ok[j]&&dist[k]+edge[j].wei<dist[edge[j].to]){
dist[edge[j].to]=dist[k]+edge[j].wei; //松弛操作
siftup(b[edge[j].to]);
}
}
}
}
int main(){
init();
shortestpath(1);
for (int i=1;i<=n;i++) cout<<dist[i]<<" "; cout<<endl;
return 0;
}参考数据：
输入：
6 11
1 2 5
1 3 30
1 4 18
2 3 12
2 4 10
3 5 25
4 1 15
4 5 8
5 2 5
5 3 20
5 6 4
输出：
0 5 17 15 23 27
样例如图
posted on 2015-08-29 15:59
龙在江湖 阅读(801)
评论(0) 编辑 收藏 引用 所属分类:
图论 、
算法