首师大附中科创教育平台 我的刷题记录 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[],book[]={};

int h[],pos[],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=;

     while(i*<=size&&flag==)

     {

          if(dis[h[i]]>dis[h[i*]]) t=i*;

          else t=i;

          if(i*+<=size)

              if(dis[h[t]]>dis[h[i*+]]) t=i*+;

          if(t!=i)

          {

              swap(t,i);

              i=t;

          }

          else flag=;

     }

     return ;

}

void siftup(int i)

{

     int flag=;

     if(i==) return ;

     while(i!=&&flag==)

     {

         if(dis[h[i]]<dis[h[i/]]) swap(i,i/);

         else flag=;

         i/=;

     }

     return ;

}

int pop()

{

    int t;

    t=h[];

    pos[t]=;

    h[]=h[size];

    pos[h[]]=;

    size--;

    siftdown();

    return t;

}

int main()

{

    int n,m,i,j,k;

    int u[],v[],w[],first[],next[];

    int inf=;

    int count=,sum=;

    scanf("%d%d",&n,&m);

    for(i=;i<=m;i++) scanf("%d%d%d",&u[i],&v[i],&w[i]);

    for(i=m+;i<=*m;i++)

    {

        u[i]=v[i-m];

        v[i]=u[i-m];

        w[i]=w[i-m];

    }

    for(i=;i<=n;i++) first[i]=-;

    for(i=;i<=*m;i++)

    {

        next[i]=first[u[i]];

        first[u[i]]=i;

    }

    book[]=;

    count++;

    dis[]=;

    for(i=;i<=n;i++) dis[i]=inf;

    k=first[];

    while(k!=-)

    {

        dis[v[k]]=w[k];

        k=next[k];

    }

    size=n;

    for(i=;i<=size;i++)

    {

        h[i]=i;

        pos[i]=i;

    }

    for(i=size/;i>=;i--)

    {

        siftdown(i);

    }

    pop();

    while(count<n)

    {

        j=pop();

        book[j]=;

        count++;

        sum+=dis[j];

        k=first[j];

        while(k!=-)

        {

            if(book[v[k]]==&&dis[v[k]]>w[k])

            {

                dis[v[k]]=w[k];

                siftup(pos[v[k]]);

            }

            k=next[k];

        }

    }

    printf("%d",sum);

}

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