ROADS  Roads
English  Vietnamese 
N cities named with numbers 1 ... N are connected with oneway roads. Each road has two parameters associated with it: the road length and the toll that needs to be paid for the road (expressed in the number of coins). Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away  to the city N. He wants to get there as quickly as possible, but he is short on cash. We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has.
Input
The input begins with the number t of test cases. Then t test cases follow. The first line of the each test case contains the integer K, 0 <= K <= 10000, maximum number of coins that Bob can spend on his way. The second line contains the integer N, 2 <= N <= 100, the total number of cities. The third line contains the integer R, 1 <= R <= 10000, the total number of roads. Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters : S is the source city, 1 <= S <= N D is the destination city, 1 <= D <= N L is the road length, 1 <= L <= 100. T is the toll (expressed in the number of coins), 0 <= T <= 100 Notice that different roads may have the same source and destination cities.
Output
For each test case, output a single line contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins. If such path does not exist, output 1.
Example
Input: 2 5 6 7 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 0 4 4 1 4 5 2 1 2 1 0 2 3 1 1 3 4 1 0 Output: 11 1
hide comments
smso:
20180627 11:23:46
3 points for dijkstra: how to tell whether state is visited, comparator for pq, ..."different roads may have the same source and destination"... (this takes the most time to debug!)


kmkhan_014:
20180517 21:34:43
AC using dijkstra. In DP ever state will be checked. In dijkstra few states are visited, also Priority Queue in STL is very fast. 

vengatesh15:
20170119 06:44:59
AC after 1 month.. 

aish_dutt:
20161021 06:37:51
Using adj list , don't forget to clear vector :) :)


itissabbir:
20160423 07:38:06
I used simple DP


Liquid_Science:
20160302 18:23:15
" Notice that different roads may have the same source and destination cities." 1 WA due to this 

naruto09:
20150925 15:50:15
getting WA...checked on most of the test cases...cant catch the problem..:(


Shubham Bansal:
20150526 20:13:04
finally a question with AC in 1 go :)


Shubham Jadhav:
20150502 22:20:58
finally, ac.. don't give up, keep trying 

shubham:
20150129 16:41:04
Last edit: 20150129 16:42:04 
Added by:  Duc 
Date:  20050428 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Central European Olympiad in Informatics '98 