Đường Đi Ngắn Nhất Trên Đồ Thị Trọng Số Dương (Dijkstra)
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề 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
NvàM(1 ≤ N ≤ 10^5,1 ≤ M ≤ 2 × 10^5). Mdòng tiếp theo: Mỗi dòng gồm 3 số nguyênu v wmô tả cạnh có hướng từuđếnvvớ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đếnN, hoặc-1nếu không thể đi tớiN.
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
Community Discussion