Problem 2169 shadow

Problem 2169 shadow

大家好,又见面了,我是全栈君。

Problem 2169 shadow
 Problem 2169 shadow

Accept: 141    Submit: 421
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem 2169 shadow Problem Description

YL是shadow国的国王,shadow国有N个城市。

为了节省开支,shadow国仅仅有N-1条道路,这N-1条道路使得N个城市连通。某一年,shadow国发生了叛乱,叛军占据了多个城市,王都岌岌可危。

王都为编号为1的城市,除了王都外有K个城市有YL的军队。如今这K支军队要向王都进军。而且消灭沿途经过的城市中的叛军。现给出N个城市的道路情况以及城市的叛军数量,问总共须要消灭多少叛军?

Problem 2169 shadow Input

第一行输入两个整数N,K,接下来输入N(1<=N<=100000)个整数Ai(0<=Ai<=10000),表示第i个城市的叛军数量。接下来输入K个大于等于1且小于等于N的整数。表示有军队的城市的编号。

数据保证王都以及有军队的城市没有叛军。接下来输入N-1行。每行两个整数u、v,表示连接u和v的一条道路。

每支军队仅仅能沿着道路走,而且是其所在城市与王都之间的最短路线走。

Problem 2169 shadow Output

输出一行一个整数表示消灭的叛军数量。

Problem 2169 shadow Sample Input

4 2

0 3 0 0

3 4

1 2

2 3

2 4

Problem 2169 shadow Sample Output

3

http://acm.fzu.edu.cn/problem.php?pid=2169

/*从有军队的城市BFS遍历,找到王都。沿途累加被杀掉的叛军数
用两个数组存储邻边关系
*/
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 100005
struct list
{
    int val;
    int nxt;
}L[N*2]; //存储相临边的关系
struct point
{
  int val;
  int k_num;  //杀死敌军数
}p,q;
int enemy[N]; //叛军
int army[N];  //国军
int vis[N];   //标记是否訪问
int head[N];
int n,k,id;
void add(int u,int v) //把u连在v后面
{
    L[id].val=v;  //保存v的值,且拥有唯一id
    L[id].nxt=head[u]; //// v的next为head[u],这里head[u]表示u的头结点的id,且把它连在v的后面
    head[u]=id++;// 此时由于u的头结点已经连在v后面了,所以要更新头结点,把head[u]换成v的id
}
int bfs(int x)
{
    int ret=0;
    queue<point>s;
    p.val=x;
    p.k_num=enemy[x];
    s.push(p);
    vis[x]=1;
    while(!s.empty())
    {
        p=s.front();
        s.pop();
        if(1==p.val)   //找到目标点
            ret=p.k_num;
        for(int i=head[p.val];i!=0;i=L[i].nxt)
        {
            int v=L[i].val;
            if(0==vis[v])
            {
                vis[v]=1;
                q.val=v;
                q.k_num=p.k_num+enemy[v];
                s.push(q);
            }
        }
    }
    return ret;
}

int main()
{
    while(scanf(“%d%d”,&n,&k)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf(“%d”,&enemy[i]);
        for(int i=1;i<=k;i++)
            scanf(“%d”,&army[i]);
        memset(vis,0,sizeof(vis));
        memset(head,0,sizeof(head));
        int ans=0;
        id=1;
        for(int i=1;i<=n-1;i++)
        {
            int u,v;
            scanf(“%d%d”,&u,&v);
            add(u,v);
            add(v,u);
        }
        for(int i=1;i<=k;i++)
        {
            if(0==vis[army[i]])
                ans+=bfs(army[i]);
        }
        printf(“%d\n”,ans);
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116046.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • win10eplan激活码破解步骤3月最新在线激活

    win10eplan激活码破解步骤3月最新在线激活,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • PXE 批量安装 Ubuntu 20.04

    PXE 批量安装 Ubuntu 20.04原文链接:https://www.cpweb.top/1698一、介绍  Ubuntu20.04的服务器安装程序支持新的操作模式:自动安装(automatedinstallation)。自动安装可以通过自动安装配置提前回答所有这些配置问题,并使安装过程无需任何交互即可运行。  在Ubuntu18.04中,用的应答文件是preseeds(预配置文件),它基于debian-installer(akadi)来实现自动安装的。需要注意的是,如果你使用的是cobbler,那你应…

  • iOS7 UIKit动力学-碰撞特性UICollisionBehavior 下

    iOS7 UIKit动力学-碰撞特性UICollisionBehavior 下

  • wait(),notify(),notifyAll()_多线程wait和sleep

    wait(),notify(),notifyAll()_多线程wait和sleep前言在上一篇中,我们介绍了Java中的线程的基本概念,我们了解到线程是有很多种状态的,本章,我们就来聊聊线程中的状态是如何进行控制与切换的。Java中提供了很多种方法对线程的状态进行控制以及线程之间的通信,包括wait、notify、notifyAll、sleep,下面我们就来看一下它们之间有什么区别,以及如何使用这些方法进行线程状态的控制与通信。线程之间的通信在Java中可以用w…

  • postman汉化包_python模拟post请求

    postman汉化包_python模拟post请求Postman安装(汉化Postman)一、下载Postman下载地址:https://www.postman.com/downloads/二、下载汉化包下载地址:https://github.com/hlmd/Postman-cn/releases注意:中文包的版本和postman的版本一定要一致,否则会出现汉化后打不开postman的情况postman设置里能看到版本号:汉化包下对应的就可以:三、解压到对应目录四、重启P…

  • 主机游戏神作和排行榜

    主机游戏神作和排行榜文章目录主机游戏任天堂、索尼、微软三大家任天堂索尼微软其他电视游戏主机(家用机)红白机时代PS时代次世代主机掌机其他游戏PC游戏平台Steam其他评分和榜单端游、页游和手游评分和榜单VR设备ValveIndexHTCViveOculusRiftSOculusQuest三星MR+权威游戏评分媒体TGAIGNGameSpot其他GameRankingsFami通MetacriticEGA游戏…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号