刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！
简答题
1.City 不 City
“City 不 City”因为一位外国友人保保熊直播旅游时总是用奇怪的腔调说“好 city，啊！”而走红中国社交网络，成为网络热梗。事实上，有一些叛逆的年轻人在旅行时会刻意避开网红打卡点，选择一些小众的特色地方小城镇，不追求 city，而喜欢说“好 country，啊”。
下面给定各个城镇的旅游热度和城镇间的旅行花销，请你为前来咨询的旅行者规划一条最经济的路线，并且尽可能避开热度很高的网红点。
时间限制：6000
内存限制：65536
输入
输入第一行首先给出 4 个正整数：n 和 m（1 < n ≤ 103，1≤ m ≤ 5n），依次为城镇数量（于是城镇编号从 1 到 n）和城镇间的通路条数；s 和 t 依次为旅行者的出发地和目的地的城镇编号。 随后一行给出 n 个不超过 100 的正整数，依次为 n 个城镇的旅游热度。 再后面是 m 行，每行给出一条通路连接的两个城镇的编号、这条通路的最小花销（其数值为不超过 103 的正整数）。通路是双向的，题目保证任一对城镇间至多给出一条通路。 同一行的数字间均以空格分隔。
输出
题目要求从 s 到 t 的最小花销路线；若这样的路线不唯一，则取途径城镇的最高旅游热度值最小的那条路线。 在一行中输出从 s 到 t 的最小花销、以及途经城镇的最高旅游热度值（若没有途经的城镇，则热度值为 0）。数值间以 1 个空格分隔，行首尾不得有多余空格。 若从 s 根本走不到 t，则在一行中输出 `Impossible`。
样例输入
样例1：
8 14 7 8
100 20 30 10 50 80 100 100
7 1 1
7 2 2
7 3 1
7 4 2
1 2 1
1 5 2
2 5 1
3 4 1
3 5 3
3 6 2
4 6 1
5 6 1
5 8 1
6 8 2
样例2：
3 1 1 2
10 20 30
1 3 1
样例输出
样例1：
4 50
样例2：
Impossible
提示
样例1解释： 从 7 到 8 的最短路径有 3 条，其中 2 条都经过城镇 1，于是对应的最高旅游热度值是城镇 1 的热度值 100。解路径为 7->2->5->8，途径城镇 2 和 5，对应的最高旅游热度值是城镇 5 的热度值 50。在最短路径长度相等的情况下，取热度值小的解，故输出的热度值为 50。
“City 不 City”因为一位外国友人保保熊直播旅游时总是用奇怪的腔调说“好 city，啊！”而走红中国社交网络，成为网络热梗。事实上，有一些叛逆的年轻人在旅行时会刻意避开网红打卡点，选择一些小众的特色地方小城镇，不追求 city，而喜欢说“好 country，啊”。
下面给定各个城镇的旅游热度和城镇间的旅行花销，请你为前来咨询的旅行者规划一条最经济的路线，并且尽可能避开热度很高的网红点。
时间限制：6000
内存限制：65536
输入
输入第一行首先给出 4 个正整数：n 和 m（1 < n ≤ 103，1≤ m ≤ 5n），依次为城镇数量（于是城镇编号从 1 到 n）和城镇间的通路条数；s 和 t 依次为旅行者的出发地和目的地的城镇编号。 随后一行给出 n 个不超过 100 的正整数，依次为 n 个城镇的旅游热度。 再后面是 m 行，每行给出一条通路连接的两个城镇的编号、这条通路的最小花销（其数值为不超过 103 的正整数）。通路是双向的，题目保证任一对城镇间至多给出一条通路。 同一行的数字间均以空格分隔。
输出
题目要求从 s 到 t 的最小花销路线；若这样的路线不唯一，则取途径城镇的最高旅游热度值最小的那条路线。 在一行中输出从 s 到 t 的最小花销、以及途经城镇的最高旅游热度值（若没有途经的城镇，则热度值为 0）。数值间以 1 个空格分隔，行首尾不得有多余空格。 若从 s 根本走不到 t，则在一行中输出 `Impossible`。
样例输入
样例1：
8 14 7 8
100 20 30 10 50 80 100 100
7 1 1
7 2 2
7 3 1
7 4 2
1 2 1
1 5 2
2 5 1
3 4 1
3 5 3
3 6 2
4 6 1
5 6 1
5 8 1
6 8 2
样例2：
3 1 1 2
10 20 30
1 3 1
样例输出
样例1：
4 50
样例2：
Impossible
提示
样例1解释： 从 7 到 8 的最短路径有 3 条，其中 2 条都经过城镇 1，于是对应的最高旅游热度值是城镇 1 的热度值 100。解路径为 7->2->5->8，途径城镇 2 和 5，对应的最高旅游热度值是城镇 5 的热度值 50。在最短路径长度相等的情况下，取热度值小的解，故输出的热度值为 50。
使用微信搜索喵呜刷题，轻松应对考试！
答案：
解析：
详细步骤：
- 构建图论模型：使用邻接矩阵或邻接链表表示图，其中每个元素(i, j)表示城镇i与城镇j之间的通路信息，包括通行花销。
- 初始化：将起点s到所有其他城镇的距离设为无穷大（表示不可达），将起点s到自身距离设为0。同时，记录从起点s出发能到达的城镇的最高旅游热度值。
- 使用Dijkstra算法：每次从未被访问的城镇中选取一个与起点s距离最小的城镇，更新其相邻城镇的距离。在更新距离时，同时记录途经的城镇的最高旅游热度值。
- 重复步骤3，直到终点t被访问或没有更多可访问的城镇为止。
- 输出结果：如果终点t被访问，则输出从起点s到终点t的最短路径长度和途经的城镇的最高旅游热度值。如果无法访问终点t，则输出"Impossible"。
注意：在记录途经的城镇的最高旅游热度值时，需要记录当前路径上的最高旅游热度值以及之前路径上的最高旅游热度值中的较大值。这样，在比较不同路径时，可以确保选取的是途径城镇的最高旅游热度值最小的路线。
创作类型：
原创
本文链接：1.City 不 City“City 不 City”因为一位外国友人保保熊直播旅游时总是用奇怪的腔调
版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！
分享考题 
