問題描述
經歷了二十多年的戰爭，人類終于打敗了異蟲，將它們徹底驅逐。大戰后的星系百廢待興，星系總督根據那句老話“要致富，先修路”，做出了修建行星間高速航道的決定，這些航道可以雙向通行。然而，由于戰爭中高能量武器的使用，空間也變得不穩定。為了防止時空亂流導致某條航道中斷，需要保證在修建主航道時必須額外修建一條輔助航道來備用，即直接相鄰的兩顆行星中間有偶數條航道。
你的任務是幫助總督找到花費最少的方案，使所有行星都能相互到達且滿足上方的條件。
輸入
輸入資料第一行為兩個正整數n,m。n 表示星系中行星的個數，m 表示可用的航道數量。接下來 m 行，每行有三個正整數 a,b,c。a,b 表示航道的兩端，c 表示修建這條航道的費用。
輸出
輸出資料僅一行，為滿足條件的方案的最小花費。如果沒有滿足條件的方案，則輸出-1。
輸入樣例
2 3
1 2 1
1 2 3
2 1 2
輸出樣例
3
提示
1、修建第一條和第三條航道，其中一條做主航道，另一條備用。
2、N<100000,M<2500000
3、直接相連指可以只經過一條航道相互到達。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/123402.html
標籤：C語言
上一篇：C語言心形圖案列印