两个吃奶一个添下面视频_人妻第一页香蕉网_欧美xxxx少妇_妺妺窝人体色www婷婷

1437 問(wèn)題 B: 藍(lán)橋杯歷屆試題-城市建設(shè)

時(shí)間限制: 1s 內(nèi)存限制: 128MB 提交: 2641 解決: 531
題目描述
棟棟居住在一個(gè)繁華的C市中，然而，這個(gè)城市的道路大都年久失修。市長(zhǎng)準(zhǔn)備重新修一些路以方便市民，于是找到了棟棟，希望棟棟能幫助他。

C市中有n個(gè)比較重要的地點(diǎn)，市長(zhǎng)希望這些地點(diǎn)重點(diǎn)被考慮。現(xiàn)在可以修一些道路來(lái)連接其中的一些地點(diǎn)，每條道路可以連接其中的兩個(gè)地點(diǎn)。另外由于C市有一條河從中穿過(guò)，也可以在其中的一些地點(diǎn)建設(shè)碼頭，所有建了碼頭的地點(diǎn)可以通過(guò)河道連接。

棟棟拿到了允許建設(shè)的道路的信息，包括每條可以建設(shè)的道路的花費(fèi)，以及哪些地點(diǎn)可以建設(shè)碼頭和建設(shè)碼頭的花費(fèi)。

市長(zhǎng)希望棟棟給出一個(gè)方案，使得任意兩個(gè)地點(diǎn)能只通過(guò)新修的路或者河道互達(dá)，同時(shí)花費(fèi)盡量小。

樣例說(shuō)明
建設(shè)第2、3、4條道路，在地點(diǎn)4、5建設(shè)碼頭，總的花費(fèi)為9。


輸入
輸入的第一行包含兩個(gè)整數(shù)n,  m，分別表示C市中重要地點(diǎn)的個(gè)數(shù)和可以建設(shè)的道路條數(shù)。所有地點(diǎn)從1到n依次編號(hào)。 
接下來(lái)m行，每行三個(gè)整數(shù)a,  b,  c，表示可以建設(shè)一條從地點(diǎn)a到地點(diǎn)b的道路，花費(fèi)為c。若c為正，表示建設(shè)是花錢的，如果c為負(fù)，則表示建設(shè)了道路后還可以賺錢（比如建設(shè)收費(fèi)道路）。 
接下來(lái)一行，包含n個(gè)整數(shù)w_1,  w_2,  …,  w_n。如果w_i為正數(shù)，則表示在地點(diǎn)i建設(shè)碼頭的花費(fèi)，如果w_i為-1，則表示地點(diǎn)i無(wú)法建設(shè)碼頭。 

輸入保證至少存在一個(gè)方法使得任意兩個(gè)地點(diǎn)能只通過(guò)新修的路或者河道互達(dá)。 


數(shù)據(jù)規(guī)模和約定
對(duì)于100%的數(shù)據(jù)，1  < =  n  < =  10000，1  < =  m  < =  100000，-1000< =c< =1000，-1< =w_i< =1000，w_i≠0。

輸出
輸出一行，包含一個(gè)整數(shù)，表示使得所有地點(diǎn)通過(guò)新修道路或者碼頭連接的最小花費(fèi)。如果滿足條件的情況下還能賺錢，那么你應(yīng)該輸出一個(gè)負(fù)數(shù)。 
樣例輸入
5 5
1 2 4
1 3 -1
2 3 3
2 4 5
4 5 10
-1 10 10 1 1
樣例輸出
9
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比賽公告

                    

                    

                        

                            六月來(lái)了！ 熱起來(lái)把！                        

                    

                

                

                    

                        
比賽狀況