TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2495
  • 题目
  • P2495【NOIP2013-D1T3】货车运输
    限制 : 时间限制 : 10000 MS   空间限制 : 128000 KB
    问题描述

    A国有n座城市,编号从1到n,城市之间有m条双向道路。
    每一条道路对车辆都有重量限制,简称限重。
    现在有q辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

    输入格式

    第一行有两个用一个空格隔开的整数 n,m,表示 A 国有n座城市和m条道路。
    接下来m行,每行3个整数x,y,z,表示从x号城市到y号城市有一条限重为z的道路(x≠y,两座城市之间可能有多条道路)
    接下来一行有一个整数 q,表示有 q 辆货车需要运货。
    接下来q行,每行两个整数x,y,之间用一个空格隔开,表示一辆货车需要从x城市运输货物到y城市(x≠y)。

    输出格式

    输出共有 q 行,每行一个整数,表示对于这一辆货车,它的最大载重是多少。
    如果货车不能到达目的地,输出-1。

    样例输入

    4 3 
    1 2 4 
    2 3 3 
    3 1 1 

    1 3 
    1 4 
    1 3 

    样例输出

    3
    -1
    3

    提示

    对于 30%的数据,1<=n<=1000,1<=m<=10000,1<=q<=1000;
    对于 60%的数据,1<=n<=1000,1<=m<=50000,1<=q<=1000;
    对于 100%的数据,1<=n<=10000,1<=m<=50000,1<=q<=30000,0<=z<=100000。