以如下格式输入数据: L1 L2 L3 C1 C2 C3 A B N a[2] a[3] …… a[N]
可能有多组测试数据,对于每一组数据, 根据输入,输出乘客从A到B站的最小花费。
1 2 3 1 2 3 1 2 2 2
2
/*动态规划法,参考了263保洁小妹大佬的代码*/ #include "stdio.h" #include "limits.h" //其中宏定义的括号要加上,因为如果在Price(x)参加运算的时候, //如果没有括号会因为优先级的问题,使得表达式的值最终等于冒号表达式的?或:后的值 #define Price(x) ((x)>l1?(x)>l2?c3:c2:c1) #define Min(x,y) ((x)<(y)?x:y) int a[1000],cost[1000]; int main(){ int l1,l2,l3,c1,c2,c3,A,B,n,i,j; while(scanf("%d%d%d%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3,&A,&B,&n) != EOF){ for(i = 2; i <= n; i++){ scanf("%d",&a[i]); } cost[A] = 0; for(i = A+1; i <= B; i++){ cost[i] = cost[i-1] + Price(a[i]-a[i-1]); }//初始化状态,认为每一站都买了票,后面再对每一站都买票的情况进行优化 for(i = A+1; i <= B; i++){ //考虑从A站到一层循环当前i站中间的所有站 //更新方法就是从i站前的每一站开始考虑,这一站到i站的花费是否可以减少 //如果i,j两地的距离小于l3,就要考虑另一种买票选择 //感觉这题和最小邮票数还挺像的。 for(j = i-1; (a[i] - a[j] <= l3) && j >= A; j--){ cost[i] = Min(cost[i],cost[j]+Price(a[i] - a[j])); } } printf("%d\n",cost[B]); } return 0; }写得程序居然进了排行榜,激动到哭泣
package tsinghua; import java.util.Scanner; /* * QQ: 825580813(一起来敲代码) */ public class MinCost { static int[] L = new int[3]; static int[] C = new int[3]; static int A, B, N; static int[] distance; //distance[i] 表示 第1站 到 第i + 1站 的距离 static int[] dp; //dp[i] 表示 第一站 到 第i + 1站 的最小花费 public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { for (int i = 0; i < L.length; ++i) { L[i] = sc.nextInt(); } for (int i = 0; i < C.length; ++i) { C[i] = sc.nextInt(); } A = sc.nextInt(); B = sc.nextInt(); N = sc.nextInt(); distance = new int[N]; for (int i = 1; i < distance.length; ++i) { distance[i] = sc.nextInt(); } int res = getMinCost(); System.out.println(res); } sc.close(); } //用动态规划的方法求出dp的值 private static int getMinCost() { dp = new int[distance.length]; dp[1] = getPrice(distance[1]); //第2站的最小花费就是 第1站 到 第2站 的花费. for (int i = 2; i < distance.length; ++i) { int interval = distance[i] - distance[i - 1]; //第i站 与 前一站 的间隔 //第i站 的初始赋值,就是前一站的花费 + 前一站 到第 i 站的花费 dp[i] = dp[i - 1] + getPrice(interval); for (int j = i - 2; j >= 0; --j) { //试探是否可以通过前几站 直接坐到 第i站(中途不下车) interval = distance[i] - distance[j];//第j站 到 第i站的间隔 if (interval > L[2]) { //如果间隔大于L3的话,j前面的站就不能直达第i站了,跳出 break; } dp[i] = Math.min(dp[i], dp[j] + getPrice(interval)); } } return dp[B - 1] - dp[A - 1]; } //根据一段距离计算出花费 private static int getPrice(int dis) { for (int i = 0; i < L.length; ++i) { if (dis <= L[i]) { return C[i]; } } return 0; } }
#include<iostream> (720)#include<algorithm> #include<string> (765)#include<map> #include<vector> (721)#include<iomanip> #include<regex> using namespace std; const int N = 1000; int dp[N]; int L1, L2, L3, C1, C2, C3; int cost(int dis) { if (dis <= L1) return C1; else if (dis <= L2) return C2; return C3; } int main() //动态规划 { int a, b; int n; while (cin >>L1>>L2>>L3) { vector<int> dis; cin >> C1 >> C2 >> C3; cin >> a >> b; cin >> n; for (int i = 0; i < n; i++) { if (i == 0) dis.push_back(0); else { int z; cin >> z; dis.push_back(z); //dis[i]--i-1->i的距离 } } a--; b--; for (int i = a; i <= b; i++) { if (i == a) dp[i] = 0; else dp[i] = 999999999; } for(int i=a;i<=b;i++) for (int j = a ; j < i; j++) { if (dis[i] - dis[j] <= L3) dp[i] = min(dp[i], dp[j] + cost(dis[i]-dis[j])); } cout << dp[b] << endl; } }
#include <cstdio> #include <algorithm> #define LL long long #define MAXN 10005 #define INF 0x3f3f3f3f using namespace std; // dp[A][B] = min(dp[A][k] + dp[k][B], C1/C2/C3) LL dp[MAXN][MAXN]; LL pre[MAXN]; int N; LL L1, L2, L3, C1, C2, C3; LL calc(int a, int b) { LL dis = pre[b] - pre[a]; if (dis <= L1) return C1; else if (dis <= L2) return C2; else if (dis <= L3) return C3; else return INF; } int main() { int A, B; scanf("%lld%lld%lld%lld%lld%lld%d%d%d", &L1, &L2, &L3, &C1, &C2, &C3, &A, &B, &N); for (int i = 2; i <= N; i++) { scanf("%lld", &pre[i]); } // dp for (int len = 1; len <= B - A; len++) { for (int lf = A; lf <= B - len; lf++) { dp[lf][lf+len] = calc(lf, lf+len); if (len > 1) { for (int k = lf + 1; k < lf+len; k++) dp[lf][lf+len] = min(dp[lf][lf+len], dp[lf][k] + dp[k][lf+len]); } } } printf("%lld\n", dp[A][B]); }
#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; int c[1000],dp[1000][1000]; int main() { int l1,l2,l3,c1,c2,c3,a,b,n; while(cin>>l1>>l2>>l3>>c1>>c2>>c3) { cin>>a>>b>>n; for(int i=2;i<=n;i++) cin>>c[i]; c[1]=0; memset(dp,INF,sizeof(dp)); for(int len = 2;len<=n;len++){//枚举长度 for(int j = 1;j+len<=n+1;j++){//枚举起点,ends<=n int ends = j+len - 1; if(c[ends]-c[j]<=l1) dp[j][ends]=c1; else if(c[ends]-c[j]<=l2) dp[j][ends]=c2; else if(c[ends]-c[j]<=l3) dp[j][ends]=c3; else { for(int i=j+1;i<ends;i++) dp[j][ends]=min(dp[j][ends],dp[j][i]+dp[i][ends]); } } } cout<<dp[a][b]<<endl; } return 0; }
import java.util.Scanner; public class LeastCost { public static void main(String[] a){ Scanner scanner =new Scanner(System.in); while (scanner.hasNext()){ int L1 =scanner.nextInt(); int L2 =scanner.nextInt(); int L3 =scanner.nextInt(); int C1 =scanner.nextInt(); int C2 =scanner.nextInt(); int C3 =scanner.nextInt(); int A =scanner.nextInt(); int B =scanner.nextInt(); int N =scanner.nextInt(); int[] Array = new int[N+1]; for(int i=2;i<=N;i++) Array[i]=scanner.nextInt(); int[] cost =new int[N+1]; for(int i=A+1;i<=B;i++) cost[i]=9999999; for (int i=A;i<=B;i++){ //一轮循环即可 int index1 =(i+NumOfStation(L1,Array,i)>=B)?B:(i+NumOfStation(L1,Array,i)); int index2 =(i+NumOfStation(L2,Array,i)>=B)?B:(i+NumOfStation(L2,Array,i)); int index3 =(i+NumOfStation(L3,Array,i)>=B)?B:(i+NumOfStation(L3,Array,i)); cost[index1]=Math.min(cost[index1],cost[i]+C1); cost[index2]=Math.min(cost[index2],cost[i]+C2); cost[index3]=Math.min(cost[index3],cost[i]+C3); } System.out.println(cost[B]); } } public static int NumOfStation(int distance,int[] array,int startpos){ //走L距离能过多少站 int countDis=0; int countStations=0; for (int i=startpos;i<array.length>distance) break; } return countStations-1; } } </array.length>
//看成最短路径问题用Dijkstra解决 #include <stdio.h> #include <limits.h> #include <vector> using namespace std; struct E{ int next; int c; }; vector<E> edge[100]; bool mark[100]; int Dis[100],a[100]; int main() { //freopen("in.txt","r",stdin); int L1,L2,L3,C1,C2,C3,A,B,n; while(scanf("%d%d%d%d%d%d",&L1,&L2,&L3,&C1,&C2,&C3)!=EOF) { scanf("%d%d%d",&A,&B,&n); for(int i=2;i<=n;i++) scanf("%d",&a[i]); //Build Graph for(int i=1;i<=n;i++) edge[i].clear(); for(int i=1;i<=n;i++){ for(int j=i+1;a[j]-a[i]<=L3 && j<=n;j++){ E tmp; if(a[j]-a[i]<=L1) tmp.c=C1; else if(a[j]-a[i]<=L2 && a[j]-a[i]>L1) tmp.c=C2; else tmp.c=C3; tmp.next=j; edge[i].push_back(tmp); } } //Dijkstra Init for(int i=1;i<=n;i++){ Dis[i]=-1; //所有距离不可达 mark[i]=false; //所有节点不属于集合K } Dis[A]=0; //第一近点为A,长度0 mark[A]=true; //将A加入集合K int newP=A; //新加入点为A //Dijkstra Main for(int i=A;i<n;i++){ //每次循环确定一个最近点 for(int j=0;j<edge[newP].size();j++){ int t=edge[newP][j].next; int c=edge[newP][j].c; if(mark[t]==true) continue; if(Dis[t]==-1 || Dis[t]>Dis[newP]+c) Dis[t]=Dis[newP]+c; } int min=INT_MAX; for(int j=A+1;j<=n;j++){ if(mark[j]==true) continue; if(Dis[j]<=-1) continue; if(Dis[j]<min){ min=Dis[j]; newP=j; } mark[newP]=true; } } printf("%d\n",Dis[B]); } return 0; }
def fareNum(distance): if distance <= length[0]: return costs[0] elif distance <= length[1]: return costs[1] else: return costs[2] try: while True: tempInput = list(map(int,input().split())) length = tempInput[:3] costs = tempInput[3:] a,b = list(map(int,input().split())) if a > b: a,b = b,a n = int(input()) distances = [0,0] #distances[i]表示第一个车站到第i个车站的路程 for i in range(n-1): distances.append(int(input())) spend = [float('inf')] * (n+1) #spend[i]表示车站a到车站i的最小花费 spend[a] = 0 for i in range(a+1,b+1): temp = i - 1 #从前一个开始查找最少花费 while temp >= a and (distances[i]-distances[temp]) <= length[2]: spend[i] = min(spend[i],spend[temp]+fareNum(distances[i]-distances[temp])) temp -= 1 print(spend[b]) except Exception: pass
思想没错,就是超时了,估计C++能过
package com.speical.first;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* 最小花费
*
* bfs 你们仅仅学习一下思想吧
* java竟然超时,c++没试
* @author special
* @date 2017年12月23日 下午2:36:19
*/
public class Pro22 {
private static int[] dis = new int[3];
private static int[] price = new int[3];
static class Node{
int index;
int sum;
public Node(int index, int sum){
this.index = index;
this.sum = sum;
}
}
public static int bfs(int start, int end, int[] tDis){
int min = Integer.MAX_VALUE;
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(start, 0));
while(!queue.isEmpty()){
Node node = queue.remove();
if(node.index == end){
min = Math.min(min,node.sum);
continue;
}
for(int i = node.index + 1; i <= end; i++){
int d = tDis[i] - tDis[node.index];
if(d > dis[2]) break;
if(d >= 0 && d <= dis[0]){
queue.offer(new Node(i, node.sum + price[0]));
}else if(d > dis[0] && d <= dis[1]){
queue.offer(new Node(i, node.sum + price[1]));
}else{
queue.offer(new Node(i, node.sum + price[2]));
}
}
}
return min;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
while(input.hasNext()){
for(int i = 0; i < 3; i++){
dis[i] = input.nextInt();
}
for(int i = 0; i < 3; i++){
price[i] = input.nextInt();
}
int start = input.nextInt();
int end = input.nextInt();
int N = input.nextInt();
int[] tDis = new int[N + 1];
for(int i = 2; i <= N; i++){
tDis[i] = input.nextInt();
}
System.out.println(bfs(start,end,tDis));
}
}
}
#include<iostream> using namespace std; int main() { int N, A, B; long long Distance[10000]; long long Dp[10000]; long long L1, L2, L3, C1, C2, C3; long long temp_length; long long temp_cost; while (cin >> L1 >> L2 >> L3 >> C1 >> C2 >> C3) { cin >> A >> B >> N; Distance[1] = 0; for (int i = 2; i <= N; ++i) cin >> Distance[i]; if (A == B) { cout << '0' << endl; continue; } if (A > B) { int temp = A; A = B; B = temp; } for (int i = A; i <= B; ++i) Dp[i] = -1; Dp[A] = 0; for (int i = A; i <= B; ++i) { for (int j = i + 1; j <= B; ++j) { temp_length = Distance[j] - Distance[i]; if (temp_length > L3) break; else if (L2 < temp_length && temp_length <= L3) temp_cost = C3; else if (L1 < temp_length && temp_length <= L2) temp_cost = C2; else temp_cost = C1; if (Dp[j] == -1 || Dp[i] + temp_cost < Dp[j]) Dp[j] = Dp[i] + temp_cost; } } cout << Dp[B] << endl; } return 0; }
#include <stdio.h> #include <limits.h> #define N 500 int dist[N], cost[N];//第i个站的总里程、最少花费 int l1, l2, l3, c1, c2, c3; int Price(int L)//L距离的票多少钱 { if(L<=l1) return c1; else if(L<=l2) return c2; else return c3; } int main() { int n, from, to; while(scanf("%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3)!=EOF) { dist[1]=0;//始发站里程为0 scanf("%d %d", &from, &to); scanf("%d", &n); for(int i=2; i<=n; i++) scanf("%d", &dist[i]); cost[from]=0;//出发之前,没花一毛钱 for(int i=from+1; i<=to; i++)//前进!!! { cost[i]=INT_MAX;//先假设到i站需要花无数的钱 for(int j=from; j<i; j++)//到i站的票可能是从j站买的 { int L=dist[i]-dist[j];//j站到i站的距离 if(L<=l3&&cost[j]+Price(L)<cost[i]) {//如果从j站买票能比以往的方案更省钱,那就从j买票 cost[i]=cost[j]+Price(L); } } } printf("%d\n", cost[to]); } return 0; }
参考了其他人的方法,给出了自己实现的代码和详细注释,希望对你有用 #include<bits/stdc++.h> using namespace std; int L1,L2,L3,C1,C2,C3,N; int A,B; int price(int dis){ if(dis<=L1) return C1; if(dis<=L2) return C2; if(dis<=L3) return C3; //其余情况不可能出现 } //1.本算法利用动态规划 //2.亦可以看成一张图,每个站点都与其他站点相连,且刚开始只知道相连站点间的花费 //然后利用图中 Dijkstra 求当前节点到每个节点的最小花费 int main(){ while(cin>>L1>>L2>>L3>>C1>>C2>>C3>>A>>B>>N){ int dis[N+1]; int cost[N+1];//cost[i] 代表从 A -> i 的最小花费 for(int i=2;i<=N;i++){ cin>>dis[i]; } //初始化 cost[A]=0; //A -> A花费为 0 for(int i=A+1;i<=B;i++){ cost[i]=INT_MAX; //A -> 其余各站的最小花费 还不知道 } //每次前进一站,并计算出 A -> 该站 的最小花费 for(int i=A+1;i<=B;i++){ //到达 i 站 前的最后一次中转站 有 i-A 个可能 for(int j=A;j<i;j++){ if(dis[i]-dis[j]<=L3){//如果从 j 站 中转一次可以到 i 站 cost[i]=min(cost[i],cost[j]+price(dis[i]-dis[j])); } } } //输出结果 cout<<cost[B]<<endl; } return 0; }
#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int l1, l2, l3, c1, c2, c3; int a, b, n; int w[N]; int dp[N]; int value(int u, int v) { int dis = w[v] - w[u]; if (dis <= l1) return c1; else if (dis <= l2) return c2; else return c3; } int main() { while (cin >> l1 >> l2 >> l3 >> c1 >> c2 >> c3) { cin >> a >> b >> n; w[1] = 0; for (int i = 2; i <= n; i++) { cin >> w[i]; } dp[1] = 0; dp[2] = value(1, 2); for (int i = 3; i <= b; i++) { dp[i] = 1e9; for (int j = 1; j < i; j++) { int dis = w[i] - w[i - j]; if (dis > l3) break; dp[i] = min(dp[i], dp[i - j] + value(i - j, i)); } } cout << dp[b] - dp[a] << endl; } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int[] a; static int L1; static int L2; static int L3; static int C1; static int C2; static int C3; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s; while ((s = br.readLine()) != null) { String[] s1 = s.split(" "); L1 = Integer.parseInt(s1[0]); L2 = Integer.parseInt(s1[1]); L3 = Integer.parseInt(s1[2]); C1 = Integer.parseInt(s1[3]); C2 = Integer.parseInt(s1[4]); C3 = Integer.parseInt(s1[5]); String[] s2 = br.readLine().split(" "); int A = Integer.parseInt(s2[0]); int B = Integer.parseInt(s2[1]); int N = Integer.parseInt(br.readLine()); a = new int[N + 1]; for (int i = 2; i <= N; i++) { a[i] = Integer.parseInt(br.readLine()); //a[i]表示第1站到第i站的距离 1~2为a[2] 1~3为a[3] ...... } //数据录入完毕 int[] dp = new int[N + 1 + A]; //dp[i]表示A到第i站的最短花费 dp[A] = 0;//A~A for (int i = A + 1; i <= B; i++) { dp[i] = Integer.MAX_VALUE; for (int j = A; j <= i; j++) { int d = a[i] - a[j]; if (d <= L3) dp[i] = Math.min(dp[i], dp[j] + cost(d)); else { // continue; int cost = 0; for (int k = j; k < i; k++) { cost += cost(a[k + 1] - a[k]); } dp[i] = Math.min(dp[i], dp[j] + cost); } //两站间距离大于L3时就跳过,不用计算 //因为要下车再买票,一直到剩下的几站距离小于等于L3为止(一定会有两站间距离小于等于L3的,因为每两个站之间的距离不超过L3) //假设要算2~9站的最少票价,乘客原本坐到了5站,发现剩余距离远大于L3,那乘客就得往后坐一站,再次做比较,发现还大于L3,继续坐一站。。。。 //直到剩余的距离小于L3,这里假设7~9的距离<L3,这种情况下我买的票情况:2~5是最少花费(dp数组)+5~6的票价+6~7的票价+7~9的票价 //这种情况下一定不是最少票价,后期一定会被2~7的最少花费(dp数组)+7~9的票价所更新 } } System.out.println(dp[B]); } } private static int cost(int distence) { int price = 0; if (distence <= L1) price = C1; else if (distence <= L2) price = C2; else price = C3; return price; } }
import java.util.Scanner; import java.util.Arrays; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); while(in.hasNext()){ //读取输入 int l1 = in.nextInt(); int l2 = in.nextInt(); int l3 = in.nextInt(); int c1 = in.nextInt(); int c2 = in.nextInt(); int c3 = in.nextInt(); int a = in.nextInt(); int b = in.nextInt(); int n = in.nextInt(); int[] counts = new int[n + 1]; for(int i= 2; i <= n; i++){ counts[i] = in.nextInt(); } //初始化辅助数组 int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[a] = 0; //求最小花费 for(int i = a + 1; i <= b; i++){ for(int j = a; j < i; j++){ int length = counts[i] - counts[j]; if(length <= l3){ int value = (length <= l1 ? c1 : (length <= l2 ? c2 : c3)); dp[i] = Math.min(dp[i], dp[j] + value); } } } System.out.println(dp[b]); } } }
#include<iostream> #include<limits.h> using namespace std; int l1,l2,l3,c1,c2,c3; int price(int d){ if(d<=l1) return c1; else if(d<=l2) return c2; else return c3; } int main(){ while(cin>>l1>>l2>>l3>>c1>>c2>>c3){ int a,b; cin>>a>>b; int n; cin>>n; int L[n+1]; L[1] = 0; for(int i=2;i<=n;i++){ cin>>L[i]; } int dp[n+1]; dp[a]=0; for(int i=a+1;i<=b;i++){ int min = INT_MAX; for(int j=a; j<i;j++){ int d = L[i]-L[j]; if(d<=l3) { dp[i]= dp[j] + price(d); if(dp[i]<min) min = dp[i]; } } dp[i] = min; } cout<<dp[b]<<endl; } return 0; }
#include <stdio.h> #include <vector> using namespace std; int l1,l2,l3,c1,c2,c3; bool mark[1000]; int dis[1000]; struct Edge { int to; int cost; }; vector graph[1000]; int help[1000]; void init(int a,int b) { for(int i=a;i<=b;i++) { mark[i] = false; graph[i].clear(); dis[i] = -1; } for(int i=a;i<=b;i++) { for(int j=i+1;j<=b;j++) { int tmp = help[j]-help[i]; Edge e; e.to = j; if(tmp<=l1) e.cost = c1; else if(tmp<=l2) e.cost = c2; else if(tmp<=l3) e.cost = c3; else continue; graph[i].push_back(e); } } } int main() { int a,b,n; while(scanf("%d%d%d%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3,&a,&b,&n)!=EOF) { for(int i=2;i<=n;i++) scanf("%d",&help[i]); init(a,b); dis[a] = 0; mark[a] = true; int newN = a; int cnt = b - a; for(int i=1;i<=cnt;i++) { for(int j=0;j<graph[newN].size();j++) { int tmp = graph[newN][j].to; int c = graph[newN][j].cost; if(mark[tmp] == true) continue; if(dis[tmp] == -1 || dis[tmp]>dis[newN]+c) dis[tmp] = dis[newN]+c; } int min=123123123; for(int j=a;j<=b;j++) { if(mark[j] == true) continue; if(dis[j] == -1) continue; if(min>dis[j]) { min = dis[j]; newN = j; } } mark[newN] = true; } printf("%d\n",dis[b]); } }
#include<iostream> (720)#include<cstdio> #include<climits> (1575)#include<vector> #include<queue> using namespace std; const int MAXN = 10000; const int INF = INT_MAX; struct edge { int to; int price; edge(){}; edge(int to, int price) :to(to), price(price){} bool operator<(const edge& e)const { return price < e.price; } }; vector<edge> graph[MAXN]; priority_queue<edge> myQueue; int len[3]; int cost[3]; int dis[MAXN]; int ex[MAXN]; //单元点最短路径,使用迪杰斯特拉算法 void Union(int n) { dis[0] = dis[1] = 0; for (int i = 1; i <= n; i++) { for (int j = i+1; j <= n; j++) { if (dis[j] - dis[i] <= len[2]) { int p = 0; for (int k = 0; k < 3; k++) { if (dis[j] - dis[i]<=len[k]) { p = cost[k]; break; } } graph[i].push_back(edge(j, p)); } } } } void Dijkstra(int s) {//从s开始 ex[s] = 0; //从s+1开始 myQueue.push(edge(s, 0)); while (!myQueue.empty()) { edge a = myQueue.top(); myQueue.pop(); int b = a.to; for (int i = 0; i < graph[b].size(); i++) { //从a到i的相关信息能够遍历到就表示这个a到i是有边的,是能够直达的 int m = graph[b][i].to; int n = graph[b][i].price; if (ex[m]>ex[b] + n) { ex[m] = ex[b] + n; //把m放进优先队列当中 myQueue.push(edge(m, ex[m])); } } } } int main() { while (cin >> len[0]) { cin >> len[1] >> len[2]; for (int i = 0; i < 3; i++) cin >> cost[i]; int s, e; cin >> s >> e; //在这一站可以选择下车也可以选择不下车,看那个费用更低 //在e一定是要下车的在s一定是要上车的 int n; scanf("%d", &n); fill(ex, ex + n + 1, INF); for (int i = 2; i <= n; i++) cin >> dis[i]; Union(n); //表示有n个站 Dijkstra(s); cout << ex[e] << endl; } return 0; }
#include<iostream> (720)#include<string> #include<string.h> (845)#include<cstdio> #include<algorithm> (831)#include<vector> #include<map> (747)#include<queue> using namespace std; #define ll int (5354)#define MAX 1000005 #define inf 0x3fffff (5387)#define mod 10000 int main() { ll l1, l2, l3, c1, c2, c3, a, b, n; while (cin >> l1 >> l2 >> l3 >> c1 >> c2 >> c3) { cin >> a >> b >> n; vector<ll> v(n + 1), dp(n + 1); for (int i = 2; i <= n; i++)cin >> v[i], dp[i] = inf; dp[a] = 0; for (int i = a; i < n; i++) { //从i车站开始 for (int j = i + 1; j <= n && v[j] - v[i] <= l3; j++) { if (v[j] - v[i] <= l1) { if (dp[i] + c1 < dp[j])dp[j] = dp[i] + c1; } else if (v[j] - v[i] <= l2) { if (dp[i] + c2 < dp[j])dp[j] = dp[i] + c2; } else if (v[j] - v[i] <= l3) { if (dp[i] + c3 < dp[j])dp[j] = dp[i] + c3; } } } cout << dp[b] << endl; } }