YLT C++ 8级 2025.03

N5664 [CIE 202503 八级 T1] 旅游规划

题目描述

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。
现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。
如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式

输入说明：输入数据的第 $1$ 行给出 $4$ 个正整数 $n$、$m$、$s$、$d$，其中 $n$（$2 \le n \le 500$）是城市的个数，顺便假设城市的编号为 $0 \sim (n-1)$；$m$ 是高速公路的条数；$s$ 是出发地的城市编号；$d$ 是目的地的城市编号。
随后的 $m$ 行中，每行给出一条高速公路的信息，分别是：城市 $1$、城市 $2$、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过 $500$。输入保证解的存在。

输出格式

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

样例

样例 1
输入：

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出：

3 40

N5665 [CIE 202503 八级 T2] 取帽子

题目描述

人们觉得戴帽子会令自己看上去很帅，所以他们不管到哪里都会戴着帽子。有一天他们去到一家餐厅，服务员把他们的帽子收集了堆起来保管。当大家要离开的时候，发现帽子被像下图那样摞起来了。于是你的任务就是帮他们排好队，使得每个人都能按顺序顺利取到自己的帽子。
已知每顶帽子的大小都不相同，并且帽子的尺寸跟帽子主人的体重有关——越重的人戴的帽子就越大。

输入格式

输入第一行给出一个正整数 $n$（$\leq 10^4$），为戴帽子的人数。
随后一行给出 $n$ 个不同的帽子尺寸，为不超过 $10^5$ 的正整数，顺序是从帽子堆的底部向上给出。
最后一行给出 $n$ 个不同的体重，顺序对应编号从 $1$ 到 $n$ 的戴帽子人。体重是不超过 $10^6$ 的正整数。一行中的数字以空格分隔。

输出格式

在一行中按照取帽子的顺序输出帽子主人的编号。数字间以 $1$ 个空格分隔，行首尾不得有多余空格。

样例

样例 1
输入：

10
12 19 13 11 15 18 17 14 16 20
67 90 180 98 87 105 76 88 150 124

输出：

3 4 8 6 10 2 1 5 9 7

提示

样例说明：第一顶帽子的尺寸是最大的 $20$，所以对应第 $3$ 个人的最大体重 $180$，于是第 $3$ 个人排在最前面。第二顶帽子的尺寸是第 $6$ 小的 $16$，对应第 $6$ 小的体重 $98$，是第 $4$ 个人，于是第 $4$ 个人下一个走。以此类推。

N5666 [CIE 202503 八级 T3] 最短工期

题目描述

一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。
现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

输入格式

首先第一行给出两个正整数：项目里程碑的数量 $N$（$\le 100$）和任务总数 $M$。这里的里程碑从 $0$ 到 $N-1$ 编号。
随后 $M$ 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。

输出格式

如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出 Impossible。

样例

样例 1
输入：

9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

输出：

18

样例 2
输入：

4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

输出：

Impossible

N5667 [CIE 202503 八级 T4] 城市间紧急救援

题目描述

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。
每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。
当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式

第一行给出 $4$ 个正整数 $n$、$m$、$s$、$d$，其中 $n$（$2 \le n \le 500$）是城市的个数，顺便假设城市的编号为 $0 \sim (n-1)$；$m$ 是快速道路的条数；$s$ 是出发地的城市编号；$d$ 是目的地的城市编号。
第二行给出 $n$ 个正整数，其中第 $i$ 个数是第 $i$ 个城市的救援队的数目，数字间以空格分隔。
随后 $m$ 行中，每行给出一条快速道路的信息，分别是：城市 $1$、城市 $2$、快速道路的长度，中间用空格分开，数字均为整数且不超过 $500$。输入保证救援可行且最优解唯一。

输出格式

第一行输出最短路径的条数和能够召集的最多的救援队数量。
第二行输出从 $s$ 到 $d$ 的路径中经过的城市编号。数字间以空格分隔。

样例

样例 1
输入：

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出：

2 60
0 1 3