网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[郑州培训2012]凯旋
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | backa.in | 输出文件 | backa.out |
【背景】
当Caesar,Pearl和他们的宠物们完成了种玫瑰的任务之后,已是黄昏。
Pearl对Caesar说:“哎呀,肚子好饿呀,Caesar我们的晚餐由谁来做呀?”
“当然由我来搞定了!”Caesar拍拍胸脯说。“但今天我也很累了,不如我们就在回家的路上找一个地方野餐吧。”
“好呀好呀!”同样工作了一天的宠物们高兴地欢呼起来。
Caesar的脸色变得严峻起来。他知道这些宠物是不好养的。宠物们会选一个最贵的地方进行野餐。
【题目描述】
Caesar专注地看着回家的地图,地图上标有n(n<=200)个野餐点和野餐点之间的直达道路以及每条道路的过路费。Caesar还知道在每一个野餐点野餐的费用。你的程序会收到一些询问(i,j)满足i<>j。对于Caesar他们当前在i野餐点,要回到位于j野餐点的家,回家路线由Caesar决定,Caesar要求你求出最小费用。(费用=过路费+路径上最贵的野餐点的费用,起点和终点也有可能成为野餐的地方)
【输入格式】
第一行n,m表示结点数和边数。边是双向的。接下来一行n个数,第i个数表示在i点野餐的费用。接下来m行,每行三个数i,j,k,表示i点与j点有一条直达路线,过路费为k。再下来一个数t单独一行,表示有t(1<=t<=40000)个询问。最后t行,每行2个数i,j,表示询问(i,j)。
【输出格式】
输出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