提高二2测试题7月16日day

1、1.最短路path.pas / path.c / path.cpp1s / 256MB给定有向图G有n个顶点，m条边，请计算顶点1到其他所有点最短路的长度。【输入格式】第 1 行：n，m 两个数字，分别表示顶点数和边数第 2 行 - 第 m+1 行：每行三个数字 x，y，z ，表示有向边xy 长度为z【输出格式】第 1 行 - 第 n-1 行：第 i 行有一个数字Di+1，表示顶点 1 到顶点 i+1的最短路长度【输入输出样例】path.inpath.out4 41 2 12【数据范围】对于50%的数据，满足 n=1000, m=10000对于 100%的数据，满足 n=10000, m=10

2、0000, 所有边权均为大于等于 0 且小于等于 15000 的整数。2.吃水不忘挖井人well.pas / well.c / well.cpp1s / 256MB瑞金城外有个小村子叫沙洲坝。在江西的时候，在那儿住过。村子里没有井，吃水要到很远的地方去挑就带领战士和乡亲们挖了一口井。解放以后，乡亲们在井旁立了一块石碑，上面刻着：“吃水不忘挖井人，时刻想念。”沙洲坝有了水井，村民吃水方便了，但是还有好多小村子的村民吃水很不方便。为了实现的目标，为了让所有村民吃水更加方便，决定在一些村子挖一些水井，在一些村子之间建设水渠，使全部的村子都能被井水覆盖，不需要再在下雨天接雨水喝。某些村子是已经拥有水井

3、的，某些村子是可以挖水井的，还有一些村子地理条件很恶劣，不仅本身没有水井，而且还无法挖水井。如果一个村子 i 没有水井，并且可以挖水井，那么挖一口水井的花费为 costi。因为地理原因，有些村子之间可以建设水渠，但也有些村子之间无法建设水渠。可以建设水渠的村子共有 m 对，将在数据中给出。由于经费比较紧张，请尽量最小化工程的总花费。【输入格式】第一行：n 一个数字，表示共有n个村子以下n行：每行一个数字 costi ， 表示第i个村子，挖水井的花费为costi。若costi = 0，说明此村庄原本就有水井；若costi = -1，说明此村庄不仅没有水井，而且无法挖水井。接下来一行一个整数 m，

4、 表示共有m对村庄之间可以建设水渠。以下m行：每行3个数字 x, y, z ，表示为x的村庄和为y的村庄之间可以建设一条水渠，花费为z。【输出格式】一个数字w，表示工程的最小总花费。【输入输出样例】【数据范围】对于50%的数据，n=2000，m=20000对于100%的数据，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个整数 N,A0,B0,L0,A1,B1,L1，要求设计一个01串 S=

5、s1s2sisN， 满足：1.si=0或 si=1，1=i=N；2.对于 S 的任何连续的长度为 L0的子串 s js j+L0-1 (1=j=N-L0+1)，0的个数大于等于 A0且小于等于 B0;3.对于 S 的任何连续的长度为 L1的子串 s js j+L1-1 (1=j=N-L1+1)，1的个数大于等于 A1且小于等于 B1;例如，N=6 , A0=1 , B0=2 , L0=3 , A1=1 , B1=1 , L1=2，则存在一个满足上述所有条件的01串 S=010101。【输入格式】仅一行，有7个整数，依次表示 N,A0,B0,L0,A1,B1,L1（3=N=1000，1=A0=B0=L0=N，1=A1=B1=L1=N），相邻两个整数之间用一个空格分隔。【输出格式】仅一行，若不存在满足所有条件的01串，则输出一个整数-1，否则输出一个满足所有条件的01串。【输入输出样例】【数据范围】对于40%的数据，满足3=N=50对于100