73. 第三帝國

0 Judge

Code: 0


\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

第三帝國

題目敘述

sprout
我到河北省來

為了雅利安人的榮耀,元首決定在統一歐洲後建立以慕尼黑為中心的第三帝國。假設當時歐洲有$N$個城市,有$M$條道路連接這些城市,為了管理方便,希望每個城市都可以有一條路徑通往首都,但是因為打仗的關係所有道路都斷了,因此他要求身為工程師的你進行道路修復。每條路修復的費用都不一樣,為了節省國庫,你希望能花越少的費用越好,請你向元首會報你最少需要多少馬克。

輸入說明

第一行有兩個數字$N,M$表示有$N$城市,$M$條損毀的道路,城市的編號為$0,1,2,...,N-1$,編號0號為首都。接下來有$M$行,每行有三個正整數(int)$A,B,C$表示$A$城市和$B$城市間有一條損毀的道路,要修復他要花費$C$馬克。

輸出說明

如果沒辦法讓所有城市和首都連通,請輸出Und doch habe ich allein,不然輸出最少需要多少馬克才能讓所有城市和首都連通。

範例輸入1

4 5
0 1 5
0 2 3
2 3 2
2 1 4
3 0 1

範例輸出1

7

範例輸入2

5 5
0 1 2
1 3 5
2 4 6
3 0 9
4 2 8

範例輸出2

Und doch habe ich allein

配分方法

  • 30% $1 \leq N \leq 1000$
  • 70% $1 \leq N \leq 100000$
  • 100% $0 \leq M \leq 1000000$

Hints

帝国的毁灭

備註

我會抓抄襲喔

Judge Setting

run-time limit: 1200 ms
memory limit: 65536000 byte
測資數量: 0