National Olympiad in Informatics, China, 2014
Day 1, Problem 2 - Enchanted Forest
To obtain the master calligrapher's true teachings, little E has decided to pay a visit to the hermit of an enchanted forest. The forest can be represented as an undirected graph with n nodes and m edges. The nodes are numbered 1, 2, 3, …, n and the edges are numbered 1, 2, 3, …, m. Initially, little E is located at node 1, and the hermit is living at node n. In order to meet the hermit, little E must first travel through this enchanted forest.
The forest is home to many goblins. Whenever a human travels along an edge, the goblins on this edge will strike. Fortunately, node 1 is home to two types of elven protectors: type A elves and type B elves. Little E can harness their powers to help him reach his goal.
As long as little E brings along enough protector elves, the goblins will not launch their attacks against him. Generally speaking, each edge e_{i} of the undirected graph is associated with two values a_{i} and b_{i}. If the number of type A elves that little E is bringing is no less than a_{i}, and if the number of type B elves that little E is bringing is no less than b_{i}, then the goblins will not attack him along this edge of the forest. If and only if little E remains unattacked on every edge that he travels through, then his journey to find the hermit will be considered successful.
Since bringing along protector elves is big burden, little E would like to know the minimum total number of elves he could bring along and still successfully reach the hermit. The total number of elves is equal to the sum of the number of type A elves and the number of type B elves.
Input Format
The first line of input contains two integers n and m representing the number of nodes and edges in the undirected graph.
For the next m lines, line i + 1 will contain 4 space-separated positive integers X_{i}, Y_{i}, a_{i}, and b_{i}, indicating that the i-th edge runs between nodes X_{i} and Y_{i}. The meanings of a_{i} and b_{i} are as explained above.
Output Format
Output a single integer: if little E can successfully reach the hermit, then output the minimum number of total elves that he will have to bring along. Otherwise if little E cannot successfully reach the hermit, then output "-1
" (without the quotation marks).
Sample Input 1
4 5 1 2 19 1 2 3 8 12 2 4 12 15 1 3 17 8 3 4 1 17
Sample Output 1
32
Explanation 1
If little E takes the path 1→2→4, he will require 19 + 15 = 34 protector elves.
If little E takes the path 1→3→4, he will require 17 + 17 = 34 protector elves.
If little E takes the path 1→2→3→4, he will require 19 + 17 = 36 protector elves.
If little E takes the path 1→3→2→4, he will require 17 + 15 = 32 protector elves.
Overall, little E will require a minimum of 32 protector elves.
Sample Input 2
3 1 1 2 1 1
Sample Output 2
-1
Explanation 2
Little E has no way of reaching node 3 from node 1. Thus, we output -1
.
Constraints
Test Case | n | m | a_{i}, b_{i} |
---|---|---|---|
1 | 2 ≤ n ≤ 5 | 0 ≤ m ≤ 10 | 1 ≤ a_{i}, b_{i} ≤ 10 |
2 | |||
3 | |||
4 | 2 ≤ n ≤ 500 | 0 ≤ m ≤ 3,000 | 1 ≤ a_{i}, b_{i} ≤ 50,000 |
5 | |||
6 | |||
7 | 2 ≤ n ≤ 5,000 | 0 ≤ m ≤ 10,000 | |
8 | |||
9 | |||
10 | |||
11 | 2 ≤ n ≤ 50,000 | 0 ≤ m ≤ 100,000 |
1 ≤ a_{i} ≤ 30 1 ≤ b_{i} ≤ 50,000 |
12 | |||
13 | |||
14 | |||
15 | 1 ≤ a_{i}, b_{i} ≤ 50,000 | ||
16 | |||
17 | |||
18 | |||
19 | |||
20 |
All Submissions
Best Solutions
Point Value: 20 (partial)
Time Limit: 3.00s
Memory Limit: 512M
Added: May 19, 2015
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
It's quiet in here...