Bài tập trung cấp về chủ đề Suffix array LCP. 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:
3 2
1 2 1
2 3 1
Đầu ra:
2
Đang tải editor...