洛谷 4779
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #define N 100010 6 #define rg register 7 using namespace std; 8 int n,m,s,tot,last[N],dis[N]; 9 struct edge{int to,pre,dis;}e[400010]; 10 struct node{ 11 int poi,dis; 12 bool operator <(const node& rhs)const {return dis>rhs.dis;} 13 }; 14 priority_queue<node>q; 15 inline int read(){ 16 int k=0,f=1; char c=getchar(); 17 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 18 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 19 return k*f; 20 } 21 inline void dijkstra(int x){ 22 for(rg int i=1;i<=n;i++) dis[i]=1e9+1; 23 q.push((node){x,dis[x]=0}); 24 while(!q.empty()){ 25 node tmp=q.top(); q.pop(); 26 int now=tmp.poi; 27 if(dis[now]!=tmp.dis) continue; 28 for(rg int i=last[now],to;i;i=e[i].pre)if(dis[to=e[i].to]>dis[now]+e[i].dis){ 29 dis[to]=dis[now]+e[i].dis; 30 q.push((node){to,dis[to]}); 31 } 32 } 33 } 34 int main(){ 35 n=read(); m=read(); s=read(); 36 for(rg int i=1;i<=m;i++){ 37 int u=read(),v=read(); 38 e[++tot]=(edge){v,last[u],read()}; last[u]=tot; 39 } 40 dijkstra(s); 41 for(rg int i=1;i<=n;i++) printf("%d ",dis[i]); 42 return 0; 43 }
手写堆的版本
1 #include<cstdio> 2 #include<algorithm> 3 #define N 100010 4 #define rg register 5 #define LL long long 6 using namespace std; 7 int n,m,s,tot,fa,son,last[N],pos[N],dis[N]; 8 struct edge{int to,pre,dis;}e[400010]; 9 struct heap{int poi,dis;}h[N]; 10 inline int read(){ 11 int k=0,f=1; char c=getchar(); 12 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 13 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 14 return k*f; 15 } 16 inline void up(int x){ 17 while((fa=x>>1)&&h[fa].dis>h[x].dis) 18 swap(h[x],h[fa]),swap(pos[h[x].poi],pos[h[fa].poi]),x=fa; 19 } 20 inline void down(int x){ 21 while((son=x<<1)<=tot){ 22 if(h[son].dis>h[son+1].dis&&son<tot) son++; 23 if(h[son].dis<h[x].dis) swap(h[son],h[x]),swap(pos[h[son].poi],pos[h[x].poi]),x=son; 24 else return; 25 } 26 } 27 inline void dijkstra(int x){ 28 for(rg int i=1;i<=n;i++) dis[i]=1e9+1; 29 h[pos[x]=tot=1]=(heap){x,dis[x]=0}; 30 while(tot){ 31 int now=h[1].poi; pos[h[tot].poi]=1; h[1]=h[tot--]; if(tot) down(1); 32 for(rg int i=last[now],to;i;i=e[i].pre)if(dis[to=e[i].to]>dis[now]+e[i].dis){ 33 dis[to]=dis[now]+e[i].dis; 34 if(!pos[to]) h[pos[to]=++tot]=(heap){to,dis[to]}; 35 else h[pos[to]].dis=dis[to]; 36 up(pos[to]); 37 } 38 } 39 } 40 int main(){ 41 n=read(); m=read(); s=read(); 42 for(rg int i=1;i<=m;i++){ 43 int u=read(),v=read(); 44 e[++tot]=(edge){v,last[u],read()}; last[u]=tot; 45 } 46 dijkstra(s); 47 for(rg int i=1;i<=n;i++) printf("%d ",dis[i]); 48 return 0; 49 }