Elearning CodePath – CTP Online Judge

Đường ngắn nhất cơ bản

DJK01

🟢 Easy #Shortest Path

## Đề bài

Cho một đồ thị có hướng gồm `n` đỉnh được đánh số từ `1` đến `n` và `m` cạnh. Cạnh thứ `i` đi từ `u` đến `v` với trọng số không âm `w`.

Với một đỉnh xuất phát `s`, hãy tìm khoảng cách ngắn nhất từ `s` đến từng đỉnh trong đồ thị.

Nếu một đỉnh không thể đi tới từ `s`, in ra `-1` cho đỉnh đó.

## Dữ liệu vào

- Dòng đầu chứa ba số nguyên `n`, `m`, `s`.
- `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 `n` dòng. Dòng thứ `i` là khoảng cách ngắn nhất từ `s` đến đỉnh `i`, hoặc `-1` nếu không đi tới được.

## Ràng buộc

- `1 <= n <= 200000`
- `0 <= m <= 300000`
- `1 <= s, u, v <= n`
- `u != v`
- `0 <= w <= 10^9`
- Có thể có nhiều cạnh cùng nối một cặp đỉnh.

## Subtask

- Subtask 1: `n <= 8`, `m <= 30`.
- Subtask 2: `n <= 2000`, `m <= 10000`.
- Subtask 3: Không có ràng buộc bổ sung.

## Ví dụ

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

```text
0
3
2
6
```

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

Từ đỉnh `1`:

- Đến `1`: khoảng cách là `0`.
- Đến `3`: đi trực tiếp `1 -> 3`, chi phí `2`.
- Đến `2`: đi `1 -> 3 -> 2`, chi phí `2 + 1 = 3`, tốt hơn cạnh trực tiếp `1 -> 2`.
- Đến `4`: đi `1 -> 3 -> 2 -> 4`, chi phí `2 + 1 + 3 = 6`.

✅ Đã AC: 1 / 2 submissions