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