1、1.最短路path.pas / path.c / path.cpp1s / 256MB給定有向圖G有n個(gè)頂點(diǎn)，m條邊，請(qǐng)計(jì)算頂點(diǎn)1到其他所有點(diǎn)最短路的長(zhǎng)度?！据斎敫袷健康?1 行：n，m 兩個(gè)數(shù)字，分別表示頂點(diǎn)數(shù)和邊數(shù)第 2 行 - 第 m+1 行：每行三個(gè)數(shù)字 x，y，z ，表示有向邊xy 長(zhǎng)度為z【輸出格式】第 1 行 - 第 n-1 行：第 i 行有一個(gè)數(shù)字Di+1，表示頂點(diǎn) 1 到頂點(diǎn) i+1的最短路長(zhǎng)度【輸入輸出樣例】path.inpath.out4 41 2 12【數(shù)據(jù)范圍】對(duì)于50%的數(shù)據(jù)，滿足 n=1000, m=10000對(duì)于 100%的數(shù)據(jù)，滿足 n=10000, m=10

2、0000, 所有邊權(quán)均為大于等于 0 且小于等于 15000 的整數(shù)。2.吃水不忘挖井人well.pas / well.c / well.cpp1s / 256MB瑞金城外有個(gè)小村子叫沙洲壩。在江西的時(shí)候，在那兒住過。村子里沒有井，吃水要到很遠(yuǎn)的地方去挑就帶領(lǐng)戰(zhàn)士和鄉(xiāng)親們挖了一口井。解放以后，鄉(xiāng)親們?cè)诰粤⒘艘粔K石碑，上面刻著：“吃水不忘挖井人，時(shí)刻想念?！鄙持迚斡辛怂迕癯运奖懔?，但是還有好多小村子的村民吃水很不方便。為了實(shí)現(xiàn)的目標(biāo)，為了讓所有村民吃水更加方便，決定在一些村子挖一些水井，在一些村子之間建設(shè)水渠，使全部的村子都能被井水覆蓋，不需要再在下雨天接雨水喝。某些村子是已經(jīng)擁有水井

3、的，某些村子是可以挖水井的，還有一些村子地理?xiàng)l件很惡劣，不僅本身沒有水井，而且還無法挖水井。如果一個(gè)村子 i 沒有水井，并且可以挖水井，那么挖一口水井的花費(fèi)為 costi。因?yàn)榈乩碓?，有些村子之間可以建設(shè)水渠，但也有些村子之間無法建設(shè)水渠?？梢越ㄔO(shè)水渠的村子共有 m 對(duì)，將在數(shù)據(jù)中給出。由于經(jīng)費(fèi)比較緊張，請(qǐng)盡量最小化工程的總花費(fèi)?！据斎敫袷健康谝恍校簄 一個(gè)數(shù)字，表示共有n個(gè)村子以下n行：每行一個(gè)數(shù)字 costi ， 表示第i個(gè)村子，挖水井的花費(fèi)為costi。若costi = 0，說明此村莊原本就有水井；若costi = -1，說明此村莊不僅沒有水井，而且無法挖水井。接下來一行一個(gè)整數(shù) m，

4、 表示共有m對(duì)村莊之間可以建設(shè)水渠。以下m行：每行3個(gè)數(shù)字 x, y, z ，表示為x的村莊和為y的村莊之間可以建設(shè)一條水渠，花費(fèi)為z。【輸出格式】一個(gè)數(shù)字w，表示工程的最小總花費(fèi)。【輸入輸出樣例】【數(shù)據(jù)范圍】對(duì)于50%的數(shù)據(jù)，n=2000，m=20000對(duì)于100%的數(shù)據(jù)，n=50000，m=200000 , 1=cost=1000，-1=z=1000well.inwell.out40-1-1-1 3 563.01串sequence.pas / sequence.c / sequence.cpp1s / 256MB給定7個(gè)整數(shù) N,A0,B0,L0,A1,B1,L1，要求設(shè)計(jì)一個(gè)01串 S=

5、s1s2sisN， 滿足：1.si=0或 si=1，1=i=N；2.對(duì)于 S 的任何連續(xù)的長(zhǎng)度為 L0的子串 s js j+L0-1 (1=j=N-L0+1)，0的個(gè)數(shù)大于等于 A0且小于等于 B0;3.對(duì)于 S 的任何連續(xù)的長(zhǎng)度為 L1的子串 s js j+L1-1 (1=j=N-L1+1)，1的個(gè)數(shù)大于等于 A1且小于等于 B1;例如，N=6 , A0=1 , B0=2 , L0=3 , A1=1 , B1=1 , L1=2，則存在一個(gè)滿足上述所有條件的01串 S=010101?！据斎敫袷健?jī)H一行，有7個(gè)整數(shù)，依次表示 N,A0,B0,L0,A1,B1,L1（3=N=1000，1=A0=B0=L0=N，1=A1=B1=L1=N），相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔?！据敵龈袷健?jī)H一行，若不存在滿足所有條件的01串，則輸出一個(gè)整數(shù)-1，否則輸出一個(gè)滿足所有條件的01串?！据斎胼敵鰳永俊緮?shù)據(jù)范圍】對(duì)于40%的數(shù)據(jù)，滿足3=N=50對(duì)于100