MMINPAID  Paid Roads
A network of m roads connects N cities (numbered from 1 to N). There may be more than one road connecting one city with another. Some of the roads are paid. There are two ways to pay for travel on a paid road i from city a_{i} to city b_{i}:
 in advance, in a city c_{i} (which may or may not be the same as a_{i});
 after the travel, in the city b_{i}. The payment is P_{i} in the first case and R_{i} in the second case. Write a program to find a minimalcost route from the city 1 to the city N.
Input
The first line of the input contains the values of N and m. Each of the following m lines describes one road by specifying the values of a_{i}, b_{i}, c_{i}, P_{i}, R_{i} (1 ≤ i ≤ m). Adjacent values on the same line are separated by one or more spaces. All values are integers, 1 ≤ m, N ≤ 10, 0 ≤ Pi, Ri ≤ 100, Pi ≤ Ri (1 ≤ i ≤ m).
Output
The first and only line of the output must contain the minimal possible cost of a trip from the city 1 to the city N. If the trip is not possible for any reason, the line must contain the word 'impossible'.
Example
Input:
4 5
1 2 1 10 10
2 3 1 30 50
3 4 3 80 80
2 1 2 10 10
1 3 2 10 50
Output:
110
hide comments
smso:
20200117 06:20:25
just bfs with state = (vertex, mask), dp is not needed 

rodman10:
20190203 04:58:15
why always wrong in test case 8，can anyone help me Last edit: 20190203 05:01:03 

kmkhan_014:
20180516 23:23:53
very conceptual problem. try visualizing the states for a node. Last edit: 20180516 23:28:05 

hammadooz:
20150307 05:34:51
Last edit: 20150313 16:07:52 
Added by:  ~!(*(@*!@^& 
Date:  20090225 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Northeastern Europe 2002 Western Subregion 