P5766 [NOI1999] Optimal Connected Subset

As is well known, we can use the Cartesian coordinate system to uniquely represent any point $P$ on the plane by an ordered pair $(x,y)$. If both $x,y$ are integers, then we call point $P$ a lattice point; otherwise, point $P$ is a non-lattice point. Let the set of all lattice points on the plane be denoted by $W$. Definition 1: For two lattice points $P_1(x_1,y_1),P_2(x_2,y_2)$, if $|x_1-x_2|+|y_1-y_2|=1$, then $P_1$ and $P_2$ are said to be adjacent, denoted by $P_1$~$P_2$. Otherwise, they are said to be non-adjacent. Definition 2: Let a point set $S$ be a finite subset of $W$, that is, $S=\{P_1,P_2,\ldots,P_n\}$ $(n \ge 1)$, where $P_i$ $(1 \le i \le n)$ belongs to $W$. We call $S$ a lattice point set. Definition 3: Let $S$ be a lattice point set. If points $R$ and $T$ belong to $S$, and there exists a finite point sequence $Q_1,Q_2,\ldots,Q_k$ satisfying: 1. $Q_i$ belongs to $S$ ($1 \le i \le k$); 2. $Q_1=R$, $Q_k=T$; 3. $Q_i$~$Q_{i+1}$ $(1 \le i \le k-1)$, i.e. $Q_i$ and $Q_{i+1}$ are adjacent; 4. For any $1 \le i

The first line contains an integer $N$, indicating the number of points in the single lattice point set $V$. In the next $N$ lines, the $i$-th line $(1 \le i \le N)$ contains three integers $X_i,Y_i,C_i$, which represent the $x$-coordinate, $y$-coordinate, and weight of the $i$-th point, respectively. Adjacent numbers on the same line are separated by one space.

Output one integer, the weight sum of the required optimal connected set.

Translated by ChatGPT 5