夏令营集训照一中提高2 day2.pdfVIP

1.最短路

path.pas/path.c/path.cpp

1s/256MB

给定有向图G有n个顶点，m条边，请计算顶点1到其他所有点最短路的长度。

【输入格式】

第1行：n，m两个数字，分别表示顶点数和边数

第2行--第m+1行：每行三个数，表示有向边xy长度为z

【输出格式】

第1行--第n-1行：第i行有一个数字D[i+1]，表示顶点1到顶点i+1

的最短路长度

【输入输出样例】

path.inpath.out

【数据范围】

对于50%的数据，满足n=1000,m=10000

对于100%的数据，满足n=10000,m=100000,所有边权均为大于等于0且

小于等于15000的整数。

2.吃水不忘挖井人

well.pas/well.c/well.cpp

1s/256MB

瑞金城外有个小村子叫沙洲坝。在江西的时候，在那儿住过。

村子里没有井，吃水要到很远的地方去挑。就带领战士和乡亲们挖了一

口井。解放以后，乡亲们在井旁立了一块石碑，上面刻着：“吃水不忘挖井

人，时刻想念”

沙洲坝有了水井，村民吃水方便了，但是还有好多小村子的村民吃水很不方

便。为了实现的目标，为了让所有村民吃水更加方便，决定在一

些村子挖一些水井，在一些村子之间建设水渠，使全部的村子都能被井水覆

盖，不需要再在下雨天接雨水喝。

某些村子是已经拥有水井的，某些村子是可以挖水井的，还有一些村子地理条

件很恶劣，不仅本身没有水井，而且还无法挖水井。如果一个村子i没有水

井，并且可以挖水井，那么挖一口水井的花费为cost[i]。

因为地理，有些村子之间可以建设水渠，但也有些村子之间无法建设水

渠。可以建设水渠的村子共有m对，将在数据中给出。

由于经费比较紧张，请尽量最小化工程的总花费。

【输入格式】

第一行：n