Elearning CodePath – CTP Online Judge

Xor path (xorpath.*)

XOR_PATH_XORPATH

🟢 Easy #General #Graph #Shortest Path #Knapsack

## 💻 Đề Bài:

Cho đồ thị liên thông, có trọng số, gồm $N$ đỉnh và $M$ cạnh. Xét $Q$ truy vấn, mỗi truy vấn thuộc một trong hai loại:

1.  **Truy vấn loại 1:** Dạng $(1, i)$. **Xóa cạnh thứ $i$** khỏi đồ thị.
2.  **Truy vấn loại 2:** Dạng $(2, u, v)$. Tìm **giá trị XOR nhỏ nhất** của một đường đi bất kỳ từ đỉnh $u$ đến đỉnh $v$. In ra giá trị nhỏ nhất tìm được hoặc $-1$ nếu không tồn tại đường đi.

### 📥 **Định dạng Input**

* **Dòng 1:** Chứa ba số nguyên dương $N, M, Q$ ($N, M, Q \le 50000$).
* **$M$ dòng tiếp theo:** Mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$ mô tả cạnh thứ $i$ từ $u_i$ đến $v_i$ với trọng số $w_i$.
* **$Q$ dòng tiếp theo:** Mỗi dòng mô tả một trong hai loại truy vấn $(1, i)$ hoặc $(2, u, v)$.

**Giới hạn:**
$$N, M, Q \le 50000$$
$$0 \le w_i < 2^{30}$$

### 📤 **Định dạng Output**

Với mỗi truy vấn loại 2, in ra giá trị XOR nhỏ nhất tìm được hoặc $-1$.

### ✨ **Ví dụ**

| Input | Output |
| :--- | :--- |
| **5 5 5** | **1** |
| 1 2 2 | **2** |
| 2 3 2 | **-1** |
| 3 4 2 | |
| 2 5 0 | |
| 5 3 1 | |
| 2 1 4 | |
| 1 4 | |
| 2 1 4 | |
| 1 2 | |
| 2 1 4 | |

#### **Subtask 1 (30%):** $M=N-1 $;  
#### **Subtask 2 (30%):** $M=N $;  
#### **Subtask 3 (30%):** $Q=1; N, w \le 1000$ ;  
#### **Subtask 4 (10%):** Không có ràng buộc nào thêm.

✅ Đã AC: 0 / 0 submissions