Elearning CodePath – CTP Online Judge

Đếm số đường đi ngắn nhất

DJK04

## Đề bài

Cho một đồ thị có hướng gồm `n` đỉnh và `m` cạnh có trọng số dương. Hãy xét các đường đi từ đỉnh `1` đến đỉnh `n`.

Bạn cần tìm:

- Độ dài đường đi ngắn nhất từ `1` đến `n`.
- Số đường đi ngắn nhất khác nhau, lấy dư theo `1000000007`.

Hai đường đi được xem là khác nhau nếu dãy cạnh được sử dụng khác nhau.

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

## 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 hai số:

- `d`: độ dài đường đi ngắn nhất, hoặc `-1` nếu không tồn tại.
- `cnt`: số đường đi ngắn nhất modulo `1000000007`, hoặc `0` nếu không tồn tại.

## 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ể liệt kê đường đi đơn.
- Subtask 2: `n <= 2000`, số đường đi ngắn nhất còn nhỏ.
- Subtask 3: Không có ràng buộc bổ sung.

## Ví dụ

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

```text
3 2
```

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

Có hai đường đi ngắn nhất từ `1` đến `4`:

- `1 -> 2 -> 4`, chi phí `1 + 2 = 3`.
- `1 -> 3 -> 4`, chi phí `1 + 2 = 3`.

Vậy độ dài là `3`, số đường đi là `2`.

✅ Đã AC: 1 / 1 submissions