QTGIFT3 - Christmas is coming

Trở lại với chuyện tình của  ĐB và TN, dù còn khá lâu mới đến Noel nhưng ĐB đã quyết định lên kế hoạch từ bây giờ để tặng cho TN một món quà giáng sinh thật tuyệt vời.

Thành phố nơi 2 người đang ở có n nút giao thông đánh số từ 1 đến n, giữa chúng có một số các đường đi trực tiếp. Đêm Noel, TN đứng chờ ở nút giao thông t, ĐB sẽ đi từ nhà (ở nút giao thông s) qua một số con đường nào đó để đến điểm hẹn.

Tất nhiên ĐB không muốn TN phải chờ lâu, nên cậu sẽ chọn đường đi ngắn nhất có thể để đến nơi. Cậu cũng muốn biết có thể đến được đó bằng bao nhiêu con đường ngắn nhất khác nhau, để đề phòng trường hợp kẹt xe, đường hỏng,… Biết rằng có ít nhất một con đường từ s tới t

Do số lượng các nút giao thông quá lớn, ĐB không tài nào tự tính toán được nên quyết định nhờ các bạn giúp. Hãy giúp ĐB không phải quay lại kiếp FA lần nữa nhé =))).

 

Input

-       Dòng thứ nhất : 3 số nguyên dương n, s, t (2 ≤ n ≤ 105, 1 ≤ s, t ≤ n, s ≠ t)

-       n dòng sau, dòng thứ i gồm 3 số nguyên dương l, r, w, có nghĩa là có các đường đi một chiều từ i đến l, i đến l + 1, ..., i đến r, mỗi con đường đó có độ dài là w (1 ≤ l ≤ r ≤ n, 1 ≤ w ≤ 106)

Output

-       Hai số nguyên dương : độ dài của đường đi ngắn nhất và số lượng đường đi ngắn nhất sau khi mod 1015, cách nhau một khoảng trắng

Ví dụ

QTGIFT3_Graph_vi
Input:
	4 1 4
	2 3 3
	3 4 5
	2 4 5
	1 2 6
Output: 8 2

Giải thích : Có 2 đường đi ngắn nhất với tổng độ dài là 8 : (1, 2, 4) và (1, 3, 4)


Added by:Kata
Date:2014-11-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2015-01-05 05:30:25 Kata
Thanks :D. I glad you enjoyed it.
2014-12-23 18:02:54 LeppyR64
Interesting problem. I can't get past the O(n^2) graph density.
2014-12-23 16:11:24 Francky
Please upload the image on spoj system.

(Kata) : Uploaded.

(Francky) : Many thanks.

Last edit: 2014-12-23 16:27:28
2014-12-23 16:11:24 Kata
Yes. You can see the image. Problem edited.

Last edit: 2014-12-23 14:09:58
2014-12-23 16:11:24 રચિત (Rachit)
Are the connections directed?
2014-12-23 16:11:24 Jasmeet Singh
Tried with Dijkstra with Min-Heap and Dijkstra's without Min-Heap (Find minimum by iterating over distance array) .. Both give TLE .. any ideas ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.