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

       约翰想让她的奶牛准备市级运动会,贝茜和她的伙伴们正在练习跨栏。她们很累,所以她们想消耗最少的能量来跨栏。
       显然,对于一头奶牛跳过几个矮栏是很容易的,但是高栏却很难。于是,奶牛们总是关心路径上最高的栏的高度。
       奶牛的训练场中有 N 个站台,分别标记为1..N。所有站台之间有M 条单向道路,第i条道路是从站台Si开始,到站台Ei,其中最高的栏的高度为Hi。无论如何跑,奶牛们都要跨栏。两个站台之间可能有多条道路相连。
      奶牛们有 T 个训练任务要完成。第 i 个任务包含两个数字 Ai 和 Bi ,表示奶牛必须从站台Ai跑到站台Bi,可以路过别的站台。奶牛们想找一条路径从站台Ai到站台Bi,使路径上最高的栏的高度最小。
      你的任务就是写一个程序,计算出路径上最高的栏的高度的最小值。

    输入格式

    第1行 : 两个整数 N, M, T
    接下来M行,每行包含三个整数,表示一条道路的起止点和其中最高的栏的高度 Si , Ei , Hi
    接下来T行,每行包含两个整数,表示任务i的起始站台和目标站台: Ai , Bi

    输出格式

    共T行 : 第i行 为一个整数,表示任务i路径上最高的栏的高度的最小值。
    如果无法到达,输出 -1。

    样例输入 1

    5 6 3
    1 2 12
    3 2 8
    1 3 5
    2 5 3
    3 4 4
    2 4 8
    3 4
    1 2
    5 1

    样例输出 1

    4
    8
    -1 

    样例输入 2

    10 10 5
    6 1 11
    10 6 1
    10 2 9
    7 5 1
    4 1 14
    1 2 8
    6 5 1
    2 1 8
    1 3 7
    2 5 12
    1 4
    7 9
    3 5
    6 2
    3 9

    样例输出 2

    -1
    -1
    -1
    11
    -1

    提示

    (1 ≤ N ≤ 300)
    (1 ≤ M ≤ 25,000)
    (1 ≤ Hi ≤ 1,000,000)
    (1 ≤ T ≤ 40,000)
    (1 ≤ Ai ≤ N; 1 ≤ Bi ≤ N)


    来源  USACO NOV2007