Elearning CodePath – CTP Online Judge

Đường ngắn nhất ít cạnh nhất

DJK02

🟢 Easy #Shortest Path

## Đề bài

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

Trong tất cả các đường đi có tổng trọng số nhỏ nhất, hãy chọn đường đi dùng ít cạnh nhất.

Hãy in ra:

- Độ dài đường đi ngắn nhất từ `1` đến `n`.
- Số cạnh ít nhất trong số các đường đi ngắn nhất đó.

Nếu không thể đi từ `1` đến `n`, in ra `-1`.

## 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

- Nếu không có đường đi, in `-1`.
- Ngược lại, in hai số `d k`, trong đó:
  - `d` là độ dài đường đi ngắn nhất.
  - `k` là số cạnh ít nhất trong các đường đi có độ dài bằng `d`.

## 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ể duyệt mọi đường đi đơn.
- Subtask 2: `n <= 2000`.
- Subtask 3: Không có ràng buộc bổ sung.

## Ví dụ

```text
5 6
1 2 2
2 5 4
1 3 3
3 5 3
1 4 1
4 5 5
```

```text
6 2
```

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

Có nhiều đường từ `1` đến `5` có tổng chi phí `6`, ví dụ `1 -> 2 -> 5`, `1 -> 3 -> 5`, `1 -> 4 -> 5`. Mỗi đường dùng `2` cạnh, nên kết quả là `6 2`.

✅ Đã AC: 2 / 11 submissions