MMINPAID - Paid Roads
题意翻译
简述: 假如有n个点(编号从1到n)和m条边。
(连接两条边可能有不止一条边)当从a点到b点时,如果之前经过c点,那么只要付P的费用,如果没有经过,就付R的费用。求1到n点最少要花多少费用。
输入: 第一行包含n和m,
然后接着m行每行都有一个a、b、c、P、R的值来描述一条边;
数据范围——
1 ≤ m, N ≤ 10, 0 ≤ Pi , Ri ≤ 100, Pi ≤ Ri (1 ≤ i ≤ m).
所有值都是整数.
输出:一行为1到n点的最小费用。
如果不存在路径,输出“ impossible ” 。
样例输入
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
样例输出
110
题目描述
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 minimal-cost route from the city 1 to the city **N**.
输入输出格式
输入格式
`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 ai, bi, ci, Pi, Ri (1 `
输出格式
```
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'.
```
输入输出样例
输入样例 #1
\n
4 5\n1 2 1 10 10\n2 3 1 30 50\n3 4 3 80 80\n2 1 2 10 10\n1 3 2 10 50
输出样例 #1
\n
110