Đề bài: Tìm đường đi nhanh nhất trong thành phố

Một thành phố có ~n~ giao lộ được đánh số từ ~1~ đến ~n~ và ~m~ con đường hai chiều kết nối các giao lộ. Mỗi con đường có một độ dài tương ứng.

Bạn là tài xế xe công nghệ, nhận được yêu cầu đón khách từ giao lộ ~s~ và đưa họ đến giao lộ ~t~. Hãy tìm quãng đường ngắn nhất để di chuyển từ ~s~ đến ~t~. Nếu không thể đến nơi, in ra NO.

Dữ liệu vào (input)

• Dòng đầu tiên chứa 4 số nguyên:
  • ~n~ ~(1 \leq n \leq 1000)~ - số giao lộ
  • ~m~ ~(1 \leq m \leq 10^5)~ - số con đường
  • ~s~ ~(1 \leq s \leq n)~ - giao lộ xuất phát
  • ~t~ ~(1 \leq t \leq n)~ - giao lộ cần đến
• ~m~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên:
  • ~u~ ~v~ ~w~ ~(1 \leq u, v \leq n, 1 \leq w \leq 10^6)~ - có con đường giữa giao lộ ~u~ và ~v~ có độ dài ~w~.

Dữ liệu ra (output)

• Nếu có đường đi từ ~s~ đến ~t~, in ra độ dài ngắn nhất.
• Nếu không thể đi đến ~t~, in NO.

Ví dụ 1

Input

5 6 1 5
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1

Output

6

Giải thích

• Lộ trình ngắn nhất từ ~1 → 5: 1 → 2 → 3 → 5~, tổng quãng đường = ~2 + 1 + 3 = 6~.

Ví dụ 2

Input

4 2 1 4
1 2 5
2 3 10

Output

NO

Giải thích

• Không có cách nào đi từ 1 đến 4, nên in "NO".

Gợi ý cách giải (thuật toán Dijkstra)

1. Dùng danh sách kề (~adj[u]~ chứa cặp ~(v, w)~) để lưu thông tin đường đi.
2. Khởi tạo khoảng cách ~dist[]~ với tất cả các giao lộ là ~∞~, riêng giao lộ xuất phát ~s~ có ~dist[s] = 0~.
3. Dùng hàng đợi ưu tiên (priority queue) để lấy đỉnh có khoảng cách ngắn nhất trước.
4. Cập nhật khoảng cách nếu tìm được đường đi tốt hơn.
5. Trả về ~dist[t]~ nếu có đường đi, ngược lại in NO.

🚀 Bài toán này giúp mô phỏng hệ thống chỉ đường GPS hoặc tìm đường đi tối ưu trong giao thông đô thị.