两段班线最低费用
拼多多 10月18号 笔试真题 第一题
拼多多真题目录点击查看: 拼多多笔试真题题库目录｜笔试题库 + 算法考点详解
题目内容
检验所要把一份冷藏试剂从发车站送到收样站。承运方不临时加站，只开若干条事先排定的固定班线。
一条班线按照行驶先后经过若干站点，站号在本线内部互不重复。试剂可以在其中某个站上车，再在更靠后的某个站下车，不能调头逆行。只要真正坐过任意一截，就要一次付清该线的整笔包车费；同一条班线至多坐一次。
冷藏条件限制了换装次数。全程最多换装一次，所以至多动用两条班线：或者单靠一条班线就把试剂从发车站带到收样站，或者先坐第一条到某个中途站，再改乘另一条送到收样站。
请算出完成这次运送的最低包车费。发车站与收样站编号相同时，试剂不必上车，费用记为 0 0 0。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/qq_45776114/article/details/168663841
