P9315 [EGOI 2021] Angry Cows / Infected Cows (No testdata yet)

Day 2 Problem C. Translated from [EGOI2021 angrycows](https://stats.egoi.org/media/task_description/2021_angrycows_en.pdf).

In recent years, the Extremely Green Cows Infection (EGOI) has spread rapidly. This disease makes cows dangerous to hikers. After several incidents, people decided to separate the cow grazing areas from the Alpine hiking areas. You are given a map of the Alps. The map has $n$ regions. Each region can be a cow grazing area, a hiking area, or an unused area. Some pairs of regions are connected by bidirectional paths. Each path has a non-negative length. (In graph theory terms, this map is an undirected weighted graph.) You may build walls in some regions. Once you build a wall in a region, neither hikers nor cows can enter that region—they can no longer pass through such a region. Your task is to choose a set of regions in which to place walls. This set must satisfy the following conditions: - It must contain only unused regions. - It must separate the cow grazing areas from the hiking areas. That is, a cow cannot travel along paths from any cow grazing area to any hiking area (without passing through a walled region). - It must **not** separate any hiking areas from each other. That is, a hiker must still be able to travel along paths from any hiking area to any other hiking area (without passing through a walled region). If there are multiple ways to achieve the goals above, we care about how convenient it is to maintain the walls. The walls will be maintained by specialized staff. Each hiking area has one such staff member stationed there. For any region $A$, define its **remoteness** as the shortest distance from $A$ to any hiking area. (The length of a path is the sum of the lengths of its paths. Note that these paths **may** pass through walls and cow grazing areas—staff have enough experience and equipment to do so.) For a set of regions, its **remoteness** is the **maximum** remoteness among all regions in the set. Among all wall placements that satisfy the requirements, find one with the minimum possible **remoteness**. If there are multiple valid solutions, you may output any one of them. Note that there is no requirement on how many regions you choose. In particular, you do **not** need to build as few walls as possible.

The first line contains two integers $n,m$ — the number of regions and the number of paths. Regions are numbered from $1$ to $n$. The second line contains $n$ integers $t_1,\ldots,t_n$, where $t_i=-1$ means region $i$ is a cow grazing area, $t_i=0$ means it is an unused area, and $t_i=1$ means it is a hiking area. The next $m$ lines each contain three integers $a_j,b_j,l_j$, meaning there is a path of length $l_j$ connecting $a_j$ and $b_j$. The input guarantees: - There is at most one path between any two regions. - Initially, from any region you can reach all regions by following paths. - There is at least one cow grazing area. - There is at least one hiking area.

If there is no valid solution, output $-1$. Otherwise, the first line contains an integer $k$ — the number of walls you build. The second line contains $k$ integers — the indices of the regions where you build walls. (The indices must be distinct numbers in $1\sim n$, and may be output in any order.) Any valid solution with minimum remoteness will be accepted.

**Notes for sample explanations** In all figures, blue (dotted border) marks hiking areas, brown-red (solid border) marks cow grazing areas, and orange-yellow (dashed border) marks walls. --- **Sample $1$ explanation**  The minimum possible remoteness is $2$. Building walls at $4,5,6$ works. Note that you cannot build walls at $4,2,6$, even though the remoteness would be $1$, because that would make hiking areas $1$ and $3$ disconnected. --- **Sample $2$ explanation**  The remoteness of region $2$ is $10^3$, and the remoteness of region $3$ is $30$, because it can be reached from $1-5-4-3$. (Recall that staff can pass through walls and cow grazing areas.) Therefore, we should build walls at $5$ and $3$ (instead of $2$), and the remoteness is then $30$. --- **Constraints** For all testdata, $2\le n\le 3\times 10^5$, $n-1\le m\le 3\times 10^5$, $t_i\in\{-1,0,1\}$, $1\le a_j < b_j\le n$, $0\le l_j\le 10^9$. - Subtask 1 ($7$ points): $n\le 10$. - Subtask 2 ($22$ points): $l_j=0$. - Subtask 3 ($16$ points): there is exactly one hiking area. - Subtask 4 ($11$ points): there are $n-1$ paths (in graph theory terms, the graph is a tree). - Subtask 5 ($8$ points): $n,m\le 2\times 10^3$, $l_j=1$. - Subtask 6 ($36$ points): no special constraints. Translated by ChatGPT 5