2049 . 龜兔賽跑

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

erd1

User's AC Ratio

75.0% (6/8)

Submission's AC Ratio

36.2% (34/94)

Tags

Description

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

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

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

比賽從城市 S 開始，T 結束

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

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

Input Format

第一行有 4 個正整數 n,m(3≤n≤3×105,n−1≤m≤3×105),S,T(1≤S,T≤n)
保證 S≠T

接下來 m 行 各有 3 個正整數 a,b(1≤a,b≤n),w(0≤w≤109)

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

保證存在從 S 到 T 的路徑

Output Format

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

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

Sample Input 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 Output 1

3 50

Sample Input 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 Output 2

3 59

Sample Input 3

2 2 1 2
1 2 10
2 2 0

Sample Output 3

-1 10

Hints

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

Problem Source

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

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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
Submit
Back to Top