图的最短路径

一、任意两点之间的最短距离已知下图中给定的关系，求出图中任意给定两点之间的最短距离输入：56151223131715492352413457输出：42二、主席的居住城市distp.pas/dist.in/dist.out【问题描述】OI国共有n个城市，任意两个城市都直接或间接连通，每两个直接相连的城市之间都有一双向公路。OI国的CHEN主席要选择其中一个城市居住，由于他到每个城市考察的概率是相等的，所以他选择的城市到其它所有城市的的最短距离的和应该最小。现在，给出城市间的道路，请帮助CHEN主席确定居住的城市。【输入数据：】Nn*n的矩阵，(i,j)表示i到j之间的距离(i,j)=(j,i)(i,j)=-1表示

i,j之间没有直接道路。【输出数据：】城市编号（如果有多个城市同时最小，输出编号最小的城市）最小距离和【输入样例：】5-131-172-131-130-170-130-176-172-176-140-170-140-1【输出样例】2234说明：数据规模：n<=100(i,j)<=100三、路径减半给定一个n（<100）个结点的带权图，可将任一条边减半，问减哪条边可以使从给定点A到给定点B的最短路径长度下降的最多。如下图，1到5的最短路径1—>3-5,最短距离：2+8=10。其中，3到5之间的距离减半变成4后，1到5的最短距离变为6，下降的最多。输入：第一行：n，A，B（<100）.中间一个空格隔开。以下n行是n*n的矩阵a[I,j]，图的权值。A[I,j]=-1表示i与j之间无边、或者i=j，其他均为小于1000的正整数。输出：选择合适的边减半后，A到B的最短距离下降的值（小数点后保留1位小数）。样例：输入：515-1627-16-1-1-182-1-1-187-1-1-16-1886-1输出：4.0四、上学路线【问题描述】小A经过初三一年的努力，终于考上了认为适合自己的山师附中。由于小A的家离学校很远，他又懒得骑自行车上学，于是他决定开学之前先考察一下上学路上的公交车路线，然后做出合适的选择，为新学期做好第一个准备。经过几天的考察，小A记下了若干路公共汽车路线，这些公共汽车都是从某个站出发，沿途依次经过很多的中间站，最后到达终点站，并且都是单向的路线。令小A感到非常不爽的是，他很难找到有一趟公共汽车能从他家直达学校，大部分是他需要先乘某一路汽车坐上几站，下来后再换乘同一站台的另一路汽车,这样换乘几次后才能到达学校。幸运的是他的家门口和学校门口都一个汽车站。小A坐车最烦的就是等车，于是他决定选择一个换乘汽车次数最少的上学路线。现在用整数1,2,...,n给所有的公共汽车站编号，约定小A的家门口的汽车站编号为1，学校门口的汽车站的编号为n。你的任务是：帮助小A寻找一个最优乘车方案,使他从家乘车到学校的过程中换车的次数最少。【输入】第一行M，表示M条单程公共汽车线路。第二行N，表示总共有N个车站。以下M行依次给出了第1条到第M条汽车线路的信息。其中第i行给出的是第i条线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。【输出】一行。如果无法乘从家到学校，则输出"NoRoud!"，否则输出你的程序所找到的最少换车次数，换车次数为0表示不需换车即可到直达·【输入输出样例】roud.inroud.out3767473612352【输入输出样例解释】乘车路线：