TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1223
  • 题目
  • P1223通讯靠吼
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    亚马逊河流域部落的人们过着非常原始的生活,他们的通讯方式基本靠吼。何老板发现他们传消息的方式非常有意思,可以称为“吼叫传递”。比如A要传话给远处的D说"我稀饭你",A会对着B大吼"我稀饭D",接着B会对着C大吼"A稀饭D",C又会对着D大吼"A稀饭你"。就这样,一个传一个,消息就传了出去。但是,如果两人之间有障碍阻隔(比如一座山、一片树林)消息就无法传递过去了。每个人的嗓音大小不同,所以喊话的声能够传递的距离也可能不同。
    何老板今天访问的部落有n个原始人,何老板将它们编号1到n,白天,它们分布在雨林的各个地方进行劳作。何老板事先告诉你哪些人之间没有障碍物间隔,可以直接喊话。
    假设每个人都不会移动位置。何老板提问说出两个人的编号x和y,你能否告诉他x要传话到y,最少几个人要吼?

    输入格式

    第一行,三个整数n,m,q。n表示共n个原始人,m表示有m对人之间无障碍阻隔,q表示何老板提问的个数。
    第二行,n个空格间隔的整数,分别表示编号1到n的人每个人喊话声最远能传递的距离(<=5000)
    接下来m行,每行三个整数x,y,z 表示编号x和编号y的人之间无障碍阻隔,他们的直线距离为z(<=5000)
    接下来q行,每行两个整数x,y表示何老板想知道x传话到y最少需要几个人吼(x可能等于y)

    输出格式

    共q行,表示对何老板提问的回答。
    对于每个提问,如果x能传话到y,输出一个整数,表示最少需要吼叫的人数。如果不能,输出"no way"

    样例输入 1

    6 9 3
    9 10 7 8 6 3
    1 2 8
    2 3 9
    1 5 7
    5 2 16
    4 3 3
    3 6 8
    5 6 6
    4 6 5
    1 4 5
    1 3   
    6 2   
    2 6 

    样例输出 1

    2
    no way
    3

    样例输入 2

    8 12 5
    14 7 30 18 33 7 8 6 
    2 7 8
    2 6 6
    3 4 10
    4 7 10
    5 8 9
    8 5 13
    3 7 6
    3 6 3
    2 8 6
    5 2 7
    3 7 10
    6 3 12
    4 5
    1 8
    3 4
    2 3
    7 3

    样例输出 2

    3
    no way
    1
    2
    1

    提示

    n<=200 m<=10000 q<=1000


    来源  by BossHe