上课笔记(4)(4)——#574. 火车票(railway)

目录

Description

Format

Input

Output

Samples

输入数据 1

输出数据 1

Limitation

题解：

程序： 

Description

从Ekaterinburg到Sverdlovsk的火车线路上有若干个站点。这条线路可以近似的表示为一条线段，火车站就是线段上的点。线路始于Ekaterinburg，终于Sverdlovsk。Ekaterinburg被标号为 1，Sverdlovsk被标号为 n。（n 为整条线路上的站点数）

线路上的任意两个站点间的直达票价是由它们间的距离决定的，票价根据以下规则制定：

如果两站的间距超过 L3​，则无直达车票。所以有时可能有必要买多张票，通过转车的方式，从一个站到达另一个站。  

例如，在上面的图中，有 7 个站点。2 号站点到 6 号站点的距离超过 L3​，不能买直达票。存在若干种中转的方法，其中的一种是买两张票：先花费 C2​ 从 22 号站到达 3 号站，然后花费 C3​ 从 3 号站到 6 号站，一种花费 C2​+C3​。

你的任务是，找出一种最经济的中转方案。

Format

Input

第一行 6 个整数 L1​,L2​,L3​,C1​,C2​,C3​ (1≤L1​

第二行一个整数 n（2≤n≤100），表示线路上的车站数。

第三行两个整数 s 和 t，分别是起点和终点的编号。注意：s 不一定小于 t。

以下的 n−1 行，按据Ekaterinburg远近，每行描述了一个车站的位置。它包含一个整数，表示该车站距Ekaterinburg的距离。

任意两个车站的距离不超过 10^9，任意两个相邻的车站的距离不超过 L3​。

Output

一个整数，表示从给定的一个站到给定的另一个站的最小花费。

Samples

输入数据 1

3 6 8 20 30 40
7
2 6
3
7
8
13
15
23

输出数据 1

70

Limitation

1s, 1024KiB for each test case.

题解：

思路和最小乘车费用差不多，就是变了个样子的完全背包，就是要好好看题目，一看挺复杂的，实际非常简单。

程序：

#include 
using namespace std;
int n,s,t,l1,l2,l3,c1,c2,c3,dp[5010],d[210];
int main(){memset(dp,0x3f,sizeof dp);//设为无穷大 cin>>l1>>l2>>l3>>c1>>c2>>c3>>n>>s>>t;//s起始站，t终点站 if(s>t)//保证s是小的 swap(s,t);for(int i=2;i<=n;i++)cin>>d[i];dp[s]=0; for(int i=s+1;i<=t;i++){for(int j=s;j

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！