233 . 最短路徑生成樹
TopCoder
Tags
Description
給出一個 $N$ 點 $M$ 邊的連通無向圖，任兩條邊的邊權皆不相同。
首先我們先從圖 $G$ 上挑選出一個生成樹 $T$。
接著對於一個點 $u$ 來說，我們稱點 $u$ 是「好點」若且唯若 $u$ 想要以最短路徑抵達圖 $G$ 上任一點都可以只透過這棵生成樹達到。
請找到一個滿足邊權總和最小的生成樹 $T'$，倘若有多個可能請選擇有最多「好點」的那棵生成樹，如果仍有很多棵樹，則可以任選一棵，並找出這個樹上有哪些好點。
Input Format
測試資料第一行包含兩個正整數 $N, M$ ，代表圖 $G$ 上的點數與邊數。
接下來一共有 $M$ 行，每行會有三個正整數 $u_i, v_i, w_i$ 代表圖上有一條 $u_i$ 到 $v_i$ 邊權為 $w_i$ 的邊。
- $1 \le N \le 3 \times 10^ 5$
- $1 \le M \le 3 \times 10^ 5$
- $1 \le u_i, v_i \le N$
- $1 \le w_i \le 10^ {12}$
Output Format
第一行請輸出一個數字 $n$ 代表你選擇的生成樹 $T'$ 上有幾個「好點」。
第二行請由小到大輸出一共 $n$ 個數字，代表生成樹 $T'$ 上每個好點的編號。
Sample Input 1
8 8
1 2 100
2 3 20
2 8 19
8 6 18
6 7 23
3 4 10
4 5 2
4 7 21
1 2 100
2 3 20
2 8 19
8 6 18
6 7 23
3 4 10
4 5 2
4 7 21
Sample Output 1
2
1 2
1 2
Hints
Problem Source
IOICamp 2021 Day5 pH
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~33 | 無額外限制 | 100 |