QBTICKET - Mua vé tàu hoả

Tác giả: skyvn97

Ngôn ngữ: C++

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
typedef long long ll;
ll len[3],cost[3],d[MAX];
ll f[MAX];
int n,s,t;
inline void minimize(ll &x,const ll &y) {
    if (x>y) x=y;
}
void init(void) {
    REP(i,3) scanf("%lld",&len[i]);
    REP(i,3) scanf("%lld",&cost[i]);
    scanf("%d%d%d",&n,&s,&t);
    FOR(i,2,n) scanf("%lld",&d[i]);
    if (s>t) swap(s,t);
}
void optimize(void) {
    memset(f,0x3f,sizeof f);
    f[s]=0;
    int id[3];
    REP(i,3) id[i]=s;
    FOR(i,s+1,t) REP(j,3) {
        while (id[j]<i && d[id[j]]<d[i]-len[j]) id[j]++;
        if (id[j]<i) minimize(f[i],f[id[j]]+cost[j]);
    }
    printf("%lld",f[t]);
}
int main(void) {
    init();
    optimize();
    return 0;
}

Download