Bài tập trung cấp về chủ đề Digit DP đếm số có tính chất. Mô hình hóa bài toán dưới dạng đồ thị vô hướng có trọng số dương. Tính khoảng cách ngắn nhất từ đỉnh 1 đến đỉnh n. In -1 nếu không tới được. Đây là bài rèn cài đặt Dijkstra với heap (O((n+m) log n)).
Dòng 1: n m. m dòng tiếp: u v w.
1 ≤ n ≤ 10^5; 0 ≤ m ≤ 2·10^5; 1 ≤ w ≤ 10^9.
Một số nguyên (-1 nếu không tới được).
Ví dụ:
Đầu vào:
5 5
1 2 2
2 3 3
3 5 1
1 4 10
4 5 1
Đầu ra:
6
Đang tải editor...