Đường Đi Ngắn Nhất Trên Đồ Thị Trọng Số Dương (Dijkstra)

Algorithms Buổi 19 — Đường đi ngắn nhất Graphs
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho đồ thị có hướng có trọng số không âm gồm N đỉnh (1..N) và M cạnh. Hãy tìm độ dài đường đi ngắn nhất từ đỉnh 1 đến đỉnh N (hoặc in -1 nếu không có đường đi).

Dữ liệu vào (Input)
  • Dòng 1: Hai số nguyên N và M (1 ≤ N ≤ 10^5, 1 ≤ M ≤ 2 × 10^5).
  • M dòng tiếp theo: Mỗi dòng gồm 3 số nguyên u v w mô tả cạnh có hướng từ u đến v với trọng số w (1 ≤ w ≤ 10^9).
Dữ liệu ra (Output)
  • In ra tổng trọng số đường đi ngắn nhất từ 1 đến N, hoặc -1 nếu không thể đi tới N.
Ví dụ mẫu
Sample Input 1
4 5
1 2 2
1 3 5
2 3 1
2 4 7
3 4 3
Sample Output 1
6
Sample Input 2
3 1
1 2 4
Sample Output 2
-1
Draft saved