潍坊昌邑一中提高1班图题目

1、1. 第二最短路径(second)已知一个图，求其中两点的第二最短路径长度。输入格式：第一行：n，m，x，y（n 顶点数30，m100 边数，x 起点，y终点）；以下 m 行，每行三个整数：i，j，k(0。输出格式：X 和y 之间的第二最短路径长度。样例输入：57121272346151样例输出：42. 最小花费(money)问题描述在n 个人中，某些人的之间可以互相转账。这些人之间转账续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几续费，请问 A 最少需要使得转账后 B 收到 100 元。输入格式：第一行：两个用空格隔开的正整数 n,m，分别表示总人数和可以互相转账的人的对数。

2、以下 m 行：每行输入三个用空格隔开的正整数 x,y,z，表示标号为x 的人和标号为 y 的人之间互相转账需要扣除 z%续费(0z100)。最后一行：两个用空格隔开的正整数 A,B。数据保证 A 与 B 之间可以直接或间接地转账。输出格式：输出 A 使得 B 到账 100 元最少需要的总费用。精确到小数点后 3位。输入样例3 31 2 12 3 21 3 31 3输出样例103.072数据范围对于 30%的数据，满足 1=n=100对于所有数据，满足 1=n 2 - 3 - 4 - 7总时间为 10 + 12 + 20 + 8 = 50，的情况是3-4 那一段，要多花 20 秒（因为行走速度减

3、半），所以这条路选需要 70 秒二：1 - 2 - 5 - 6 - 4 - 7总时间为 10 + 10 + 12 + 13 + 8 = 53，的情况是 6-4 那一段，要多花 13 秒（因为行走速度减半），所以这条路选需要 66 秒三：1 - 7总时间为 34 = 34，的情况是 1-7 那一段，要多花 34 秒（因pyramid.inpyramid.out7 81 2 102 3 123 4 204 7 81 7 342 5 105 6 126 4 1366需要 68 秒为行走速度减半），所以这条路选4.观光路线(trip)问题描述岛的 Adelton 城镇上有一个旅游机构。他们决定在提在供

4、许多的其他吸引之外，再向客人们提供旅游本镇的服务。为了从提供的吸引服务中尽可能地获利，这个旅游机构接受了一个精明决定：在相同的起点和终点之间找出一条最短路线。你的任务是编写一个程序来找这样的一条路线。在这个镇上，有N 个1 至 N），两个路口（路口之间可以有多条道路连接，有 M 条道路（为 1 至M）。但没有一条道路从一个路口出发又回到同一个路口。每一条观光线路都是由一些路组成的，这些道路序号是：y_1,y_k，且 k2。第 y_i（1=i=k-1）是连接第 x_i路口和第x_i+1号路口的；其中第 y_k 号路是连接第x_k号路口和第 x_1 号路口。而且所有的这些 x_1,x_k 分别代号表不同路口的序号。在某一条观光线所有道路的长度的和就是这条观光线路的总长度。换言之 L(y_1)+L(y_2)+L(y_k)的和就是该条光线路的长度。你的程序必须计算出观光线路的最小长度，或者说这个城镇上不存在这样的观光线路。输入格式：第一行路口的个数 N(N=100)；道路的数目 M（M10000）。接下来的每一行描述一条路，每一行有三个正整数：这条路连接，以及这条路的长度(小于 500 的正整数)。的两个路口的输出格式：如果观光路线不存在的话就输出”No solution”，否则输出观光路线的最小长度。