45 . 外星人的陰謀

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

66.7% (14/21)

Submission's AC Ratio

26.1% (30/115)

Tags

ioicamp ioicamp-2024

Description

IOI 2222 即將在粄條巿舉行！粄條市由 $N$ 個區域組成，並且有 $M$ 條高架橋，每條高架橋都是單向的從某一個區域到另一個區域，且有各自所需的通過時間，而且這些高架橋有一個特色，就是無論從任何一個區域 $v$ 開始，都無法經過至少一條高架橋，最後回到區域 $v$。選手們住在區域 $1$，而比賽場地在區域 $N$。

然而由於各種事故，IOI 2222 延期到 12 月舉行，正逢粄條歡樂耶誕城期間，因此主辦單位必須妥善安排交通路線，以避免塞車導致比賽延後。為此，主辦單位會選擇一條從區域 $1$ 到區域 $N$，由若干高架橋組成的需要花費最長時間的路線（粄條市很先進，從一條高架橋抵達一個區域後，總是可以瞬間到達任何一條離開這個區域的高架橋，因此一條路線所需花費的時間就是每條高架橋需要的通過時間總和），主辦單位覺得這樣的路線人潮肯定最少。不過這樣的選擇可能有很多，主辦單位想知道最長的所需花費時間有多長，以及這樣的路線有幾條。

你以為這題會那麼簡單嗎？其實有一群害怕人類科技發展過快的外星人，他們覺得 IOI 2222 的選手都太聰明了，因此希望把他們卡在車陣當中（事實上，IOI 2222 延期到 12 月也是他們的陰謀）。預期到這件事的主辦單位，猜測外星人可能會讓粄條市裡的某一個區域暫時無法通行，主辦單位想知道，對於每個區域 $i$，要是區域 $i$ 無法通行的話，從區域 $1$ 到 $N$ 的最長所需花費時間，以及需要最多時間的路線有幾條。由於數量可能很大，請輸出數量除以 $10^ 9+7$ 的餘數。

Input Format

第一行有兩個整數 $N$、$M$，分別代表粄條市裡的區域數量和高架橋數量。

接下來有 $M$ 行，其中第 $i$ 行包含三個正整數 $u_i,v_i,w_i$，代表第 $i$ 條高架橋是從區域 $u_i$ 到 $v_i$，通過需要的時間是 $w_i$。

  • $3 \leq N \leq 5 \times 10^ 5$
  • $1 \leq M \leq 5 \times 10^ 5$
  • $1 \leq u_i,v_i \leq N$
  • $1 \leq w_i \leq 10^ 9$
  • 從任意一個區域 $v$ 出發，都無法經過至少一條高架橋，最後回到區域 $v$
  • 從區域 $1$ 出發，可以經過若干高架橋後抵達區域 $N$

Output Format

輸出 $N$ 行，對於其中第 $i$ 行

  • 如果從區域 $1$ 沿著高架橋到 $N$ 的必定要經過區域 $i$，輸出 $-1$。
  • 否則，輸出兩個非負整數 $l_i,c_i$，代表如果第 $i$ 個區域無法通行，從區域 $1$ 到 $N$ 的最長所需花費時間是 $l_i$，需要最長時間的路線數量 $\bmod 10^ 9+7$ 是 $c_i$。

如果你輸出的最長所需花費時間都正確（包含輸出 $-1$ 的情形），但路線數量錯誤，那你會獲得 $60\%$ 的分數。（注意你輸出的 $c_i$ 仍必須是 $< 10^ 9+7$ 的非負整數，才能獲得部份分數。）

Sample Input 1

6 7
1 2 1
2 3 1
3 4 1
4 6 1
1 3 2
1 5 1
5 6 1

Sample Output 1

-1
4 1
2 1
2 1
4 2
-1

Sample Input 2

6 7
1 2 1
2 3 1
3 4 1
4 6 1
1 3 1
1 5 1
5 6 1

Sample Output 2

-1
3 1
2 1
2 1
4 1
-1

Sample Input 3

5 5
1 2 1
2 3 1
3 4 1
4 5 1
1 5 10

Sample Output 3

-1
10 1
10 1
10 1
-1

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資。 0
2 3~16 $N,M \leq 1000$。 15
3 17~29 對於 $1 \leq i < N$，都存在一條從第 $i$ 個區域到第 $i+1$ 個區域的高架橋。 42
4 0~44 無特別限制。 43

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 262144 65536 1 4
1 4000 262144 65536 1 4
2 4000 262144 65536 1 4
3 4000 262144 65536 2 4
4 4000 262144 65536 2 4
5 4000 262144 65536 2 4
6 4000 262144 65536 2 4
7 4000 262144 65536 2 4
8 4000 262144 65536 2 4
9 4000 262144 65536 2 4
10 4000 262144 65536 2 4
11 4000 262144 65536 2 4
12 4000 262144 65536 2 4
13 4000 262144 65536 2 4
14 4000 262144 65536 2 4
15 4000 262144 65536 2 4
16 4000 262144 65536 2 4
17 4000 262144 65536 3 4
18 4000 262144 65536 3 4
19 4000 262144 65536 3 4
20 4000 262144 65536 3 4
21 4000 262144 65536 3 4
22 4000 262144 65536 3 4
23 4000 262144 65536 3 4
24 4000 262144 65536 3 4
25 4000 262144 65536 3 4
26 4000 262144 65536 3 4
27 4000 262144 65536 3 4
28 4000 262144 65536 3 4
29 4000 262144 65536 3 4
30 4000 262144 65536 4
31 4000 262144 65536 4
32 4000 262144 65536 4
33 4000 262144 65536 4
34 4000 262144 65536 4
35 4000 262144 65536 4
36 4000 262144 65536 4
37 4000 262144 65536 4
38 4000 262144 65536 4
39 4000 262144 65536 4
40 4000 262144 65536 4
41 4000 262144 65536 4
42 4000 262144 65536 4
43 4000 262144 65536 4
44 4000 262144 65536 4
Submit
Back to Top