Bài tập trung cấp về chủ đề Z-function đếm match. 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 0
Đầu ra:
-1
Đang tải editor...