编程介的小学生 2016-12-14 01:50 采纳率: 20.5%
浏览 922
已采纳

Paid Roads

Description

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 ai to city bi:

in advance, in a city ci (which may or may not be the same as ai);
after the travel, in the city bi.
The payment is Pi in the first case and Ri in the second case.

Write a program to find a minimal-cost 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 ai, bi, ci, Pi, Ri (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 file 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’.

Sample 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
Sample Output

110

  • 写回答

1条回答 默认 最新

  • threenewbee 2016-12-14 02:07
    关注

    http://www.hankcs.com/program/algorithm/poj-3411-paid-roads.html

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题？

  • Paid Roads 网络
    2017-10-23 13:37
    回答 1 已采纳 http://blog.csdn.net/zhaosdfa/article/details/31051773
  • ROADS less
    2017-10-28 01:19
    回答 1 已采纳 http://blog.csdn.net/u012870383/article/details/38315953
  • Jungle Roads less 网络
    2017-09-02 08:51
    回答 1 已采纳 可参考： http://blog.csdn.net/xiaofeng187/article/details/62887975
  • Paid Roads
    2019-06-24 02:17
    weixin_33811961的博客 Problem Description A network of m roads connects N cities (numbered from 1 to N). There may be more than one road connecting one city with ... Some of the roads are paid. There are two ways t...
  • Building roads
    2017-05-19 07:34
    回答 2 已采纳 http://www.bubuko.com/infodetail-250945.html
  • Constructing Roads 网络
    2017-08-29 12:19
    回答 1 已采纳 http://blog.csdn.net/x_iya/article/details/8907560
  • Building Roads
    2017-12-03 05:37
    回答 1 已采纳 http://blog.csdn.net/u010536683/article/details/12451437
  • （POJ 3411）Paid Roads <DFS>
    2017-01-04 13:15
    STILLxjy的博客 Paid Roads DescriptionA 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 ...
  • Calculate Roads
    2017-04-04 07:26
    回答 1 已采纳 http://blog.csdn.net/wanghandou/article/details/70169023
  • POJ-3411 Paid Roads 搜索优化
    2020-07-09 18:22
    Y先森吖的博客 一个道路网连接了N个城市(从1个城市到N个城市)，可能有一条以上的道路连接一个城市和另一个城市。有些道路是有偿的。从城市Ai到城市Bi，有两种方式支付旅行费用: 在城市Ci提前支付pi(Ci可能不等于Ai);...
  • POJ3411-Paid Roads【class】
    2011-08-15 18:07
    北大POJ3411-Paid Roads【class】 解题报告+AC代码
  • POJ 3411 Paid Roads
    2016-08-18 08:03
    哆啦AC梦的博客 题目大意： 每行给定五个整数ai, bi, ci, Pi, Ri，点的个数不超过10个意思是如果一个人要从a点到达b点，如果他之前经过了c点那么花费为p，否则花费为r。问他要从1到n点最少花费是多少？ ...
  • Paid Roads POJ - 3411
    2017-09-11 21:55
    weixin_33819479的博客 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...
  • POJ 3411 Paid Roads (状压DP)
    2018-12-04 00:05
    Sqwlly的博客 Paid Roads 题意：111到nnn的最小花费，aaa到bbb的花费为，如果经过ccc为ppp，否则为rrr。 题解：dp[i][j]dp[i][j]dp[i][j]表示以jjj结尾状态为iii时的最小花费，则有dp[i∣1&amp;lt;&amp;lt;a][b]=min(dp[i...
  • Paid Roads----DFS
    2017-02-09 00:30
    bless295的博客 Paid Roads Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7023   Accepted: 2602 Description A network of m roads connects N cities (numbered ...
  • Paid Roads（DFS）
    2014-07-29 16:57
    userluoxuan的博客 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 ...
  • POJ-3411 Paid Roads
    2016-04-07 22:32
    RJ28的博客 Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6472   Accepted: 2398 Description ...A network of m roads connects N cities (numbered from 1 to N). There may be more than
  • poj 3411 Paid Roads
    2019-09-29 23:50
    B218707的博客 题意：有N个城市M条路相连，有两种收费方式，一种是在城市Ci时收费为Pi，另一种是在城市Bi中Ri，求从城市1到城市N的最小花费。其中Pi要小于Ri。 思路：其实我觉得这就是一道变形的最短路问题，虽然是用的深搜，但...
  • POJ3411-Paid Roads
    2011-08-15 18:08
    小優YoU的博客 全解题报告索引目录 -> 【北大ACM – POJ试题分类】 转载请注明出处：http://exp-blog.com ------------------------------------------------------------------------- ...有些路是要收费的...
  • Poj 3411 Paid Roads（最短路）
    2017-03-07 16:08
    wang2147483647的博客 题目地址：http://poj.org/problem?id=3411 思路：记录状态，松弛操作时判断即可。 #include #include #include #include #include #define debug using namespace std; const int maxn=15; ...
  • 没有解决我的问题, 去提问

悬赏问题

  • ¥15 求解O-S方程的特征值问题给出边界层布拉休斯平行流的中性曲线
  • ¥15 谁有desed数据集呀
  • ¥20 手写数字识别运行c仿真时，程序报错错误代码sim211-100
  • ¥15 关于#hadoop#的问题
  • ¥15 (标签-Python|关键词-socket)
  • ¥15 keil里为什么main.c定义的函数在it.c调用不了
  • ¥50 切换TabTip键盘的输入法
  • ¥15 可否在不同线程中调用封装数据库操作的类
  • ¥15 微带串馈天线阵列每个阵元宽度计算
  • ¥15 keil的map文件中Image component sizes各项意思