[THHV 2016 - CLC - 11] Bài 2: Lộ trình
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Hoàng Anh học xa trường của mình, ngày nào em cũng dậy rất sớm để chuẩn bị đi học, nhưng địa bàn nơi Hoàng Anh sống lại phức tạp, có nhiều nút giao nhau và nhiều con đường nối các nút giao thông này. Có hai loại con đường là đường 1 chiều và đường 2 chiều. Độ dài mỗi con đường là một số nguyên dương. Nhà Hoàng Anh ở nút giao thông 1 còn trường ở nút giao thông ~N~. Vì đường đi của Hoàng Anh đến trường gặp nhiều yếu tố như đi qua sông, đi qua công trường xây dựng,… phải giảm tốc độ nên Hoàng Anh muốn biết có tất cả bao nhiêu lộ trình ngắn nhất từ nhà tới trường.
Yêu cầu: Xác định độ dài đường đi ngắn nhất và số lượng đường đi ngắn nhất từ nút 1 đến nút ~N~.
Input
- Dòng thứ nhất ghi hai số nguyên ~N~ và ~M~.
- ~M~ dòng tiếp theo, mỗi dòng ghi 4 số nguyên dương ~K, U, V, L~. Trong đó:
- ~K = 1~ có nghĩa là có đường đi một chiều từ ~U~ đến ~V~ với độ dài ~L~.
- ~K = 2~ có nghĩa là có đường đi hai chiều giữa ~U~ và ~V~ với độ dài ~L~.
Output
- Ghi hai số là độ dài đường đi ngắn nhất và số lượng đường đi ngắn nhất.
Sample Input 1
4 3
1 1 2 1
2 2 3 3
1 1 4 2
Sample Output 1
2 1
Bình luận
Số đường đi nằm trong phạm vi số nguyên 64-bit có dấu.