图论练习题(2)

1、图论练习题（2）题1  服务点设置(djsa.pas/c/cpp):8000/vijos/Problem_Show.asp?id=1516问题描述为了进一步普及九年义务教育，政府要在某乡镇建立一所希望小学，该乡镇共有n个村庄，村庄间的距离已知，请问学校建在哪个村庄最好？（好坏的标准是学生就近入学，即在来上学的学生中，以最远的学生走的路程为标准。或者说最远的学生与学校的距离尽可能的小。）【输入格式】输入由若干行组成，第一行有两个整数，n（1n50）、m（1mn*n）；n表示村庄数，m表示村庄间道路数。第2至m+1行是每条路的信息，每行三个整数，为道路的起点、终点和两村庄间距离。（村庄从

2、0开始编号） 【输出格式】一个整数，学校所在村庄编号(如果两个村庄都适合建立学校，选择编号小的村庄建学校)。6 80 2 100 4 300 5 1001 2 52 3 503 5 104 3 204 5 604题2  双服务点设置(djsb.pas/c/cpp):8000/vijos/Problem_Show.asp?id=1517问题描述为了进一步普及九年义务教育，政府要在某乡镇建立两所希望小学，该乡镇共有n个村庄，村庄间的距离已知，请问学校建在哪两个村庄最好？（好坏的标准是学生就近入学，即在来上学的学生中，以最远的学生走的路程为标准。或者说最远的学生与学校的距离尽可能的小。）【

3、输入格式】输入由若干行组成，第一行有两个整数，n（1n50）、m（1mn*n）；n表示村庄数，m表示村庄间道路数。第2至m+1行是每条路的信息，每行三个整数，为道路的起点、终点和两村庄间距离。（村庄从0开始编号）【输出格式】两个整数，学校所在村庄编号(如果两个以上村庄都适合建立学校，选择编号小的两个村庄建学校，输出时按编号从小到大输出)。6 80 2 100 4 300 5 1001 2 52 3 503 5 104 3 204 5 600 3题3 弗洛伊德算法(fld.pas/c/cpp):8000/vijos/Problem_Show.asp?id=1518【问题描述】过暑假了，阿杜准备出

4、行旅游，他已经查到了某些城市的两两之间的距离及可行路线，如下图所示。请你编程计算从任意两个城市间的最短路径以帮助阿杜制定旅行计划。1042531055020601003010【输入格式】 输入由若干行组成，第一行有四个整数，n（1n50）、m（1mn*n）、v（1mn）、u（1mn）；城市数，m城市间道路数，v是起始城市，u是终止城市。第2至m+1行是每条路的信息，每行三个整数，为道路的起点、终点和两城市间距离。（城市从0开始编号）【输出格式】 共两行 第一行：最短路径节点编号序列 第二行：最短路径距离 如果没有通路输出 no6 8 0 50 2 100 4 300 5 1001 2 52 3

5、 503 5 104 3 204 5 60043560题4 starhder的旅游:8000/vijos/Problem_Show.asp?id=1476、源程序名 Travel.? (PAS,C,CPP)可执行文件名 Travel.exe输入文件名 Travel.in输出文件名 Travel.outstarhder突发奇想，要去G地，于是他搞来了一张地图，看怎么走才好。地图上有很多城市，G地也是一座城市。每两座城市之间都可能有直达方法，也有可能两座城市之间并不能直接相通，而要通过其他的城市转达。对于两个城市之间的直达方法，需要一定的时间，当然，如果从A城市到B城市的直达方法需要T时间，那么从

6、B城市到A城市的直达方法也是T时间。starhder想要用最短的时间到达G地，但是有个问题，他发现，地图上有些城市对他很有吸引力。所以他要在经过这些城市的基础上时间最短。starhder已经用1、2、3、4、5n标记了他可能经过的城市（1代表出发地，n代表G地），但是眼花缭乱的地图让他感到烦恼。他请你来解决这个问题，告诉他最小需要多少时间到达G地。输入输入文件的第一行是三个正整数n和m，t，n表示总共有多少个城市（包括出发地和G地），城市数不会超过200个；m是城市的直达路线数（1<=m<=20000），t表示一定去的城市数0<=t<=10（不包括出发地和G地）。接下来一行有t个整数，表示一定要去的城市。接下来m行，每行包含三个正整数，前两个数表示分别代表一个城市，第三个数是这两个城市之间的直达时间。直达时间不会超