青少年软件编程（C语言）等级考试试卷（八级）
分数：100  题数：4
一、编程题(共4题，共100分)
1.    最短路径问题
平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。
  若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是出从一点到另一点之间的最短路径。
时间限制：1000
内存限制：131072
输入
共n+m+3行，其中: 第一行为整数n。 第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。 第n+2行为一个整数m，表示图中连线的个数。 此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。 最后一行：两个整数s和t，分别表示源点和目标点。
输出
仅一行，一个实数（保留两位小数），表示从s到t的最短路径长度。
样例输入
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
样例输出
3.41
2.    Freda的越野跑
Freda报名参加了学校的越野跑。越野跑共有N人参加，在一条笔直的道路上进行。这N个人在起点处站成一列，相邻两个人之间保持一定的间距。比赛开始后，这N个人同时沿着道路向相同的方向跑去。换句话说，这N个人可以看作x轴上的N个点，在比赛开始后，它们同时向x轴正方向移动。
假设越野跑的距离足够远，这N个人的速度各不相同且保持匀速运动，那么会有多少对参赛者之间发生“赶超”的事件呢？
时间限制：1000
内存限制：262144
输入
第一行1个整数N。 第二行为N 个非负整数，按从前到后的顺序给出每个人的跑步速度。 对于50%的数据，2<=N<=1000。 对于100%的数据，2<=N<=100000。
输出
一个整数，表示有多少对参赛者之间发生赶超事件。
样例输入
5
1 3 10 8 5
样例输出
7
提示
字符串长度17模式串长度8
我们把这5个人依次编号为A,B,C,D,E，速度分别为1,3,10,8,5。 在跑步过程中： B,C,D,E均会超过A，因为他们的速度都比A快； C,D,E都会超过B，因为他们的速度都比B快； C,D,E之间不会发生赶超，因为速度快的起跑时就在前边。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。