[THUSC 2019] 补给计划

Luogu

IDLGP10339

Time1000ms

Memory512MB

DifficultyP5

2019THUSC

T 国一共有 $N$ 个城市（城市编号从 $1$ 到 $N$），这些城市被 $M$ 条双向道路所连接，每条道路有各自的长度（均大于 $0$）。共有 $K$ 个城市受灾，T 国政府计划从首都（$1$ 号城市）向这 $K$ 个城市各派出一支救援队，同时为了更好地完成救助，T 国政府计划在一些城市建立补给点。然而由于受到地理与资金等因素的影响，并不是每个城市都能建立补给点（一个城市能否建立补给点与其是否是首都或受灾城市无关）。为了尽快完成救助，这 $K$ 支救援队都只会按照最短路径前往自己的目的城市，T 国政府希望在能够建立补给点的城市中建立尽量少的补给点，使得每只救援队至少有一条到其目的城市的最短路径会经过至少一个补给点。现在告诉你 T 国的城市与道路信息，你需要计算出 T 国政府至少需要建立多少个补给点。 ## Input 输入的第一行包含三个整数 $N,M,K$，含义见题目描述，保证 $1 \le N \le 200, 0 \le M \le 10000, 1 \le K \le 20$。第二行有 $N$ 个整数，每个数为 $0$ 或者 $1$，依次表示对应的城市能否建立补给点（$1$ 表示可以建立补给点）。第三行有 $K$ 个正整数 $x_i$，表示受灾的城市编号，保证这 $K$ 个数各不相同且首都不会受灾，$1 \le x_i \le N$。接下来 $M$ 行，每行三个整数 $u,v,w$，表示城市 $u$ 和城市 $v$ 之间存在一条长度为 $w$ 的道路，$1 \le u,v \le N, 0 < w \le 10^9$。输入保证一定存在至少一个方案满足题目描述的要求。 ## Output 输出一个整数表示答案。 [samples] ## Background T 国是一个小国，受百年一遇的寒流影响，现在一些城市受到了严重的影响，T 国政府打算从首都派出救援队对受灾城市进行救助，同时建立若干补给点对救援队提供支持。 ## Note **【样例解释 1】** 该样例对应的图形如下，其中 $1$ 号点是首都，$3,4,6$ 号点是受灾城市： ![](https://cdn.luogu.com.cn/upload/image_hosting/64qspivj.png) 该样例至少需要修建 $2$ 个补给点，可以分别建在 $2,5$ 或者 $2,6$ 。注意不能修建在 $3,5$ 号点，因为从首都到 $4$ 号点的最短路径只能是 $1 \rightarrow 2 \rightarrow 4$，不存在经过 $3,5$ 号点的最短路。 **【子任务】** | 测试点 | $N$ | $M$ | $K$ | 特殊性质 | | :--:|:--:|:--:|:--:|:--:| | $1\cdots 2$ | $1 \le N \le 200$ | $M=N-1$| $1 \le K \le 20$ | 输入是一棵树 | | $3\cdots 6$ | $1 \le N \le 200$ | $0 \le M \le 10000$ | $1 \le K \le 4$ | 无 | | $7\cdots 12$ | $1 \le N \le 200$ | $0 \le M \le 10000$ | $1 \le K \le 16$ | 无 | | $13\cdots 20$ | $1 \le N \le 200$ | $0 \le M \le 10000$ | $1 \le K \le 20$ | 无 |

Samples

Input #1

6 6 3
0 1 1 1 1 1
3 4 6
1 2 2
2 3 3
2 4 4
1 5 3
5 4 4
5 6 3

Output #1

Input #2

7 6 3
0 1 1 1 1 1 1
3 4 6
1 2 1
2 4 1
2 5 1
5 6 5
1 3 2
1 7 5

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[THUSC 2019] 补给计划",
    "description": {
      "content": "T 国一共有 $N$ 个城市（城市编号从 $1$ 到 $N$），这些城市被 $M$ 条双向道路所连接，每条道路有各自的长度（均大于 $0$）。 共有 $K$ 个城市受灾，T 国政府计划从首都（$1$ 号城市）向这 $K$ 个城市各派出一支救援队，同时为了更好地完成救助，T 国政府计划在一些城市建立补给点。 然而由于受到地理与资金等因素的影响，并不是每个城市都能建立补给点（一个城市能否建立补给点",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10339"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "T 国一共有 $N$ 个城市（城市编号从 $1$ 到 $N$），这些城市被 $M$ 条双向道路所连接，每条道路有各自的长度（均大于 $0$）。\n\n共有 $K$ 个城市受灾，T 国政府计划从首都（$1$ 号城市）向这 $K$ 个城市各派出一支救援队，同时为了更好地完成救助，T 国政府计划在一些城市建立补给点。\n\n然而由于受到地理与资金等因素的影响，并不是每个城市都能建立补给点（一个城市能否建立补给点...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments