首页 > 代码库 > 首师大附中科创教育平台 我的刷题记录 0325 50212228海岛帝国：LYF的太空运输站
首师大附中科创教育平台 我的刷题记录 0325 50212228海岛帝国：LYF的太空运输站
今天给大家献上“D”级题：50212228海岛帝国：LYF的太空运输站！！
| ||||||||||||||
|
好的，以上就是50212228海岛帝国：LYF的太空运输站的题目要求，现在献上代码！！！当当当！！！
#include<iostream>using namespace std;int dis[20],book[20]={0};int h[20],pos[20],size;void swap(int x,int y){ int t; t=h[x]; h[x]=h[y]; h[y]=t; t=pos[h[x]]; pos[h[x]]=pos[h[y]]; pos[h[y]]=t; return ;}void siftdown(int i){ int t,flag=0; while(i*2<=size&&flag==0) { if(dis[h[i]]>dis[h[i*2]]) t=i*2; else t=i; if(i*2+1<=size) if(dis[h[t]]>dis[h[i*2+1]]) t=i*2+1; if(t!=i) { swap(t,i); i=t; } else flag=1; } return ;}void siftup(int i){ int flag=0; if(i==1) return ; while(i!=1&&flag==0) { if(dis[h[i]]<dis[h[i/2]]) swap(i,i/2); else flag=1; i/=2; } return ;}int pop(){ int t; t=h[1]; pos[t]=0; h[1]=h[size]; pos[h[1]]=1; size--; siftdown(1); return t;}int main(){ int n,m,i,j,k; int u[30],v[30],w[30],first[20],next[30]; int inf=9999999; int count=0,sum=0; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d%d%d",&u[i],&v[i],&w[i]); for(i=m+1;i<=2*m;i++) { u[i]=v[i-m]; v[i]=u[i-m]; w[i]=w[i-m]; } for(i=1;i<=n;i++) first[i]=-1; for(i=1;i<=2*m;i++) { next[i]=first[u[i]]; first[u[i]]=i; } book[1]=1; count++; dis[1]=0; for(i=2;i<=n;i++) dis[i]=inf; k=first[1]; while(k!=-1) { dis[v[k]]=w[k]; k=next[k]; } size=n; for(i=1;i<=size;i++) { h[i]=i; pos[i]=i; } for(i=size/2;i>=1;i--) { siftdown(i); } pop(); while(count<n) { j=pop(); book[j]=1; count++; sum+=dis[j]; k=first[j]; while(k!=-1) { if(book[v[k]]==0&&dis[v[k]]>w[k]) { dis[v[k]]=w[k]; siftup(pos[v[k]]); } k=next[k]; } } printf("%d",sum);}
首师大附中科创教育平台 我的刷题记录 0325 50212228海岛帝国：LYF的太空运输站
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。