过路费 （最短路）

过路费

问题描述

有一天你来到了一个奇怪的国家，它有 N 个城市，城市之间有若干条双向道路连接，每条道路都有一定的费用，经过城市也要一定的费用。从一个城市到达另一个城市的总花费为路径上费用最大的城市费用（包括起点和终点）加上路径上所有的道路的费用。给出 Q 次询问，分别回答每次询问中两城市间的最少花费。保证城市之间可以互达。

输入格式

第一行两个整数 N，M，表示有 N 个城市 M 条道路。
接下来 N 行每行一个整数，表示城市的费用 ci。
接下来 M 行每行三个整数，x，y，z，表示城市 x 和城市 y 间有一条费用为 z 的道路。
接下来一行一个整数 Q，表示询问次数。
接下来 Q 行每行两个整数 x，y（x 不等于 y），表示询问从城市 x 到城市 y 的最小花费。

输出格式

共 Q 行每行一个整数，第 i 行的整数表示第 i 次询问的答案。

样例输入

3 3
1
3
2
1 2 1
2 3 1
1 3 3
2
1 3
1 3

样例输出

5
5

数据规模

对于 30%的数据，N<=10，M<=20，Q<=5。
对于 60%的数据，N<=200，M<=4000，Q<=100。
对于 100%的数据，N<=300，M<=40000，Q<=100000，1<=ci<=100000，1<=z<=1000。

鉴于n这么小，当然要枚举最大点权。

做法一：改进floyd
注意到floyd算法的三层循环，那么假设外层为$k$，内层为$i,j$，那么此时经过的点必定属于 {1,2,3,…,k}⋃{i，j

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！