P2700 逐个击破

    • 305通过
    • 815提交
  • 题目提供者 Created_equal1 管理员
  • 评测方式 云端评测
  • 标签 图论 树形结构
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    三大战役的平津战场上,傅作义集团在以北平、天津为中心,东起唐山西至张家口的铁路线上摆起子一字长蛇阵,并企图在溃败时从海上南逃或向西逃窜。为了就地歼敌不让其逃走,毛泽东制定了先切断敌人东西两头退路然后再逐个歼灭敌人的战略方针。秉承伟大军事家的战略思想,作为一个有智慧的军长你,遇到了一个类似的战场局面。

    题目描述

    现在有N个城市,其中K个被敌方军团占领了,N个城市间有N-1条公路相连,破坏其中某条公路的代价是已知的,现在,告诉你K个敌方军团所在的城市,以及所有公路破坏的代价,请你算出花费最少的代价将这K个地方军团互相隔离开,以便第二步逐个击破敌人。

    输入输出格式

    输入格式:

    第一行包含两个正整数n和k。

    第二行包含k个整数,表示哪个城市别敌军占领。

    接下来n-1行,每行包含三个正整数a,b,c,表示从a城市到b城市有一条公路,以及破坏的代价c。城市的编号从0开始。

    输出格式:

    输出一行一个整数,表示最少花费的代价。

    输入输出样例

    输入样例#1: 复制
    5 3
    1 2 4
    1 0 4
    1 3 8
    2 1 1
    2 4 3
    输出样例#1: 复制
    4

    说明

    【数据范围】

    10%的数据:2≤n≤10;

    100%的数据:2≤n≤100000,2≤k≤n,1≤c≤1000000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。