[郑州培训2012]凯旋

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 backa.in 输出文件 backa.out

【背景】

CaesarPearl和他们的宠物们完成了种玫瑰的任务之后,已是黄昏。

PearlCaesar说:“哎呀,肚子好饿呀,Caesar我们的晚餐由谁来做呀?”

“当然由我来搞定了!”Caesar拍拍胸脯说。“但今天我也很累了,不如我们就在回家的路上找一个地方野餐吧。”

“好呀好呀!”同样工作了一天的宠物们高兴地欢呼起来。

Caesar的脸色变得严峻起来。他知道这些宠物是不好养的。宠物们会选一个最贵的地方进行野餐。

【题目描述】

Caesar专注地看着回家的地图,地图上标有nn<=200)个野餐点和野餐点之间的直达道路以及每条道路的过路费。Caesar还知道在每一个野餐点野餐的费用。你的程序会收到一些询问(ij)满足i<>j。对于Caesar他们当前在i野餐点,要回到位于j野餐点的家,回家路线由Caesar决定,Caesar要求你求出最小费用。(费用=过路费+路径上最贵的野餐点的费用,起点和终点也有可能成为野餐的地方)

【输入格式】

第一行nm表示结点数和边数。边是双向的。接下来一行n个数,第i个数表示在i点野餐的费用。接下来m行,每行三个数ijk,表示i点与j点有一条直达路线,过路费为k。再下来一个数t单独一行,表示有t(1<=t<=40000)个询问。最后t行,每行2个数ij,表示询问(ij)。

【输出格式】

 输出t行,依次为每个询问的答案。每个答案都不会超过2^31-1.

【样例输入】

5 7
3 4 5 4 3
1 2 6
2 3 2
3 4 2
4 5 6
1 5 10
1 4 7
2 5 7
5
1 3
2 4
3 5
1 4
2 3

【样例输出】

13
9
13
11
7

【来源】

中小学电脑报 NOI导刊 NOIP2012河南省实验中学培训 Day4 Exercise Problem 5