Elearning CodePath – CTP Online Judge

Vé giảm giá

DJK05

🟢 Easy #Shortest Path

## Đề bài

Cho một đồ thị có hướng gồm `n` đỉnh và `m` cạnh. Bạn cần đi từ đỉnh `1` đến đỉnh `n`.

Bạn có đúng một vé giảm giá. Vé này có thể được dùng nhiều nhất một lần trên một cạnh bất kỳ trong hành trình. Nếu cạnh có trọng số `w`, sau khi dùng vé, chi phí đi qua cạnh đó trở thành `floor(w / 2)`.

Bạn có thể không dùng vé nếu không cần.

Hãy tìm chi phí nhỏ nhất để đi từ `1` đến `n`.

## Dữ liệu vào

- Dòng đầu chứa hai số nguyên `n`, `m`.
- `m` dòng tiếp theo, mỗi dòng chứa ba số nguyên `u`, `v`, `w`, mô tả cạnh có hướng từ `u` đến `v` với trọng số `w`.

## Dữ liệu ra

In ra chi phí nhỏ nhất. Nếu không thể đi từ `1` đến `n`, in ra `-1`.

## Ràng buộc

- `2 <= n <= 200000`
- `0 <= m <= 300000`
- `1 <= u, v <= n`
- `u != v`
- `1 <= w <= 10^9`

## Subtask

- Subtask 1: `n <= 8`, có thể thử mọi đường đi và vị trí dùng vé.
- Subtask 2: `n <= 2000`.
- Subtask 3: Không có ràng buộc bổ sung.

## Ví dụ

```text
3 3
1 2 10
2 3 10
1 3 30
```

```text
15
```

## Giải thích ví dụ

Có thể đi `1 -> 2 -> 3` và dùng vé ở một trong hai cạnh trọng số `10`, chi phí là `5 + 10 = 15`.

Nếu đi trực tiếp `1 -> 3` và dùng vé, chi phí cũng là `15`.

✅ Đã AC: 1 / 2 submissions