TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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。

    サンプル入力 1

    4 3 
    1 2 4 
    2 3 3 
    3 1 1 

    1 3 
    1 4 
    1 3 

    サンプル出力 1

    3
    -1
    3

    サンプル入力 2

    5 7
    4 3 4440
    3 1 22348
    1 3 28368
    2 4 25086
    5 3 6991
    4 3 10638
    3 1 11106
    4
    4 5
    1 3
    5 4
    2 5

    サンプル出力 2

    6991
    28368
    6991
    6991

    ヒント

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