Bài tập trung cấp về chủ đề Aho-Corasick 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:
6 7
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
1 6 100
2 5 5
Đầu ra:
5
Đang tải editor...