TopCoder

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

26.6% (21/79)

Tags

Description

在龜兔國裡面,有一座森林,在這個森林之中有 $ n $ 座城市,之間以 $ m $ 條雙向的道路連接。

小龜和小兔想要比賽跑步,但是因為他們實力差距太大,所以造成比賽不公平。

所以他們決定小兔必須禮讓小龜,小龜至多可以選一座城市 $ x $ ,並且規定在比賽的過程中,小兔不能經過這座城市。
不過為了使比賽能夠進行,小龜不能選擇小兔一定要經過的城市,不然就不用比了...

比賽從城市 $ S $ 開始,$ T $ 結束

為了最快跑到終點,小龜和小兔都會選擇盡可能短的路徑跑到終點,當然 這兩段路徑的長度差距,全部都掌握在小龜的手中。

聰明的你 可以告訴小龜,選擇哪一座城市可以使得小兔多跑最多嘛?

Input Format

第一行有 4 個正整數 $ n, m (3 \leq n \leq 3 \times 10^ 5 , n-1 \leq m \leq 3 \times 10^ 5 ), S, T (1 \leq S, T \leq n) $
保證 $ S \neq T $

接下來 m 行 各有 3 個正整數 $ a, b(1 \leq a, b \leq n), w(0 \leq w \leq 10^ 9 )$

代表有一條連接城市 $a, b$ 的道路 其長度為 $w$

保證存在從 $ S $ 到 $ T $ 的路徑

Output Format

請輸出一個正整數代表小龜最好的 $ x $ 以及在規定下,小兔要完成比賽最少要跑多遠(數字間以空白隔開

如果有多組答案 請輸出編號最小的
如果在條件之下,小龜沒有任何選擇,那請輸出 -1

Sample Input

### Sample 1
9 10 1 5
1 2 2
2 3 4
2 6 3
2 7 5
3 4 8
6 8 9
4 8 20
7 9 10
4 9 100
4 5 16
### Sample 2
7 9 1 5
1 2 10
2 7 20
2 3 10
3 7 2
3 6 5
6 7 3
3 4 10
4 6 16
4 5 10
### Sample 3
2 2 1 2
1 2 10
2 2 0

Sample Output

### Sample 1
3 50
### Sample 2
3 59
### Sample 3
-1 10

Hints

題目並沒有保證最短路徑會唯一喔!
題解

Problem Source

如果測資有問題
請通知我
by kevin_zhang

Subtasks

No. Testdata Range Constraints Score
1 0~21 $n, m \leq 1000 $ 25
2 0~63 no additional limits 75

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 256000 65536 1 2
1 2000 256000 65536 1 2
2 2000 256000 65536 1 2
3 2000 256000 65536 1 2
4 2000 256000 65536 1 2
5 2000 256000 65536 1 2
6 2000 256000 65536 1 2
7 2000 256000 65536 1 2
8 2000 256000 65536 1 2
9 2000 256000 65536 1 2
10 2000 256000 65536 1 2
11 2000 256000 65536 1 2
12 2000 256000 65536 1 2
13 2000 256000 65536 1 2
14 2000 256000 65536 1 2
15 2000 256000 65536 1 2
16 2000 256000 65536 1 2
17 2000 256000 65536 1 2
18 2000 256000 65536 1 2
19 2000 256000 65536 1 2
20 2000 256000 65536 1 2
21 2000 256000 65536 1 2
22 2000 256000 65536 2
23 2000 256000 65536 2
24 2000 256000 65536 2
25 2000 256000 65536 2
26 2000 256000 65536 2
27 2000 256000 65536 2
28 2000 256000 65536 2
29 2000 256000 65536 2
30 2000 256000 65536 2
31 2000 256000 65536 2
32 2000 256000 65536 2
33 2000 256000 65536 2
34 2000 256000 65536 2
35 2000 256000 65536 2
36 2000 256000 65536 2
37 2000 256000 65536 2
38 2000 256000 65536 2
39 2000 256000 65536 2
40 2000 256000 65536 2
41 2000 256000 65536 2
42 2000 256000 65536 2
43 2000 256000 65536 2
44 2000 256000 65536 2
45 2000 256000 65536 2
46 2000 256000 65536 2
47 2000 256000 65536 2
48 2000 256000 65536 2
49 2000 256000 65536 2
50 2000 256000 65536 2
51 2000 256000 65536 2
52 2000 256000 65536 2
53 2000 256000 65536 2
54 2000 256000 65536 2
55 2000 256000 65536 2
56 2000 256000 65536 2
57 2000 256000 65536 2
58 2000 256000 65536 2
59 2000 256000 65536 2
60 2000 256000 65536 2
61 2000 256000 65536 2
62 2000 256000 65536 2
63 2000 256000 65536 2