首师大附中科创教育平台 我的刷题记录 0325 50212228海岛帝国：LYF的太空运输站

今天给大家献上“D”级题：50212228海岛帝国：LYF的太空运输站！！

试题编号：0325

50212228海岛帝国：LYF的太空运输站

难度级别：D； 运行时间限制：40ms； 运行空间限制：256000KB； 代码长度限制：2000000B

试题描述

    最近，“购物券”WHT在“药师傅”帝国资源大会上提出了“SSTS”太空运输站计划。由于恐怖分子前些日子刚猖狂完，炸毁高楼无数，YSF不得不执行WHT丧心病狂的计划，“演员”KLINT（众所周知，又一大土豪同学）捐赠了众多资源，和高级技术。太空运输站建成了，YSF任命LYF为站长，LJX为副站长。第一波运输计划开始了！可是，当运输军队到达中转站金星时，遭到了盗取新技术的恐怖分子的袭击。由于没有足够的兵力，整个舰队全军覆没，LYF损失惨重，恼羞成怒，随即决定让YSM和LJX调用一半星际舰队。可恐怖分子太强，再次损失惨重。YSF无奈，决定给“过路费”。但YSF是个贪财的人，所以，YSF想让给的钱最少。他把这个难题交给了LYF，LYF又把这个任务交给了LJX，所以请你帮帮可怜的LYF，帮他编一个程序。另外，悬赏10000000000000000000000000000000000$，所以赶快做吧！

输入

* 第一行：两个整数：n表示有n个城市，m表示有m条道路。
* 接下来的m行，每行三个整数：a，b，c表示从a星到达b星的路花费是c

输出

输出需要钱数最少方案

输入示例

6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2

输出示例

19

其他说明

我并没有开玩笑，钱找LJX或YSF这两个财政部部长要都可以
生成树 Prim 呵呵呵
n<=15,m<=18
40ms够了吧？

 好的，以上就是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);
}