TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5920
  • 問題
  • P5920导航路线
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 1s,128m
    問題説明

    何老板打算开车从1号城市出发去N号城市 。
    他打开手机地图,想找一条合适的路线。 地图上显示共N座城市(编号1到N)由M单向道路相连,每条道路上均显示有两个信息:通过该道路所需的时间和在该道路上行驶所需的过路费。
    何老板想尽快到达终点,但他只有K块钱,为此,他需要寻找一条从城市1到城市N在他能支付的前提下的所需时间最少的路线。请你帮他导航!

    入力形式

    第一行一个整数K
    第二行一个整数N
    第三行一个整数M
    随后的 M 行每行描述一条道路,包含 4个整数(X,Y,L,T),分别是道路的起点, 道路的终点,通过该道路所需时间, 通过该道路所需支付的费用。

    出力形式

    一个整数,表示所需最短时间,若无解,则输出“NO”;

    サンプル入力 1




    1 2 2 3 
    2 4 3 3 
    3 4 2 4 
    1 3 4 1 
    4 6 2 1 
    3 5 2 0 
    5 4 3 2 

    サンプル出力 1

    11

    サンプル入力 2

    15
    12
    16
    1 8 20 0
    1 2 10 0
    2 8 5 0
    1 7 100 0
    2 3 5 1
    3 4 5 1
    4 5 5 1
    5 6 5 1
    6 12 5 1
    8 12 10 20
    8 9 1 1
    9 10 1 1
    10 11 1 1
    11 7 2 10
    7 12 10 1
    11 4 1 0

    サンプル出力 2

    30

    ヒント

    对于100%的数据 1 ≤ N ≤ 100 ,1 ≤ K ≤1000 ,1 ≤ M ≤10000 1 ≤ X,Y ≤N , 0 ≤ L,T ≤100