B. Ant Man

题目链接

Codeforces Round #366 (Div. 1)--B. Ant Man

题解

中档题。题意大概是给定一堆数据,经过一系列复杂的操作后可以转化为两两之间的费用,指定起点终点,要求在遍历每个节点的情况下费用最小。
首先将路径指定为起点至终点,之后依次插入节点贪心,在已有路径上找到某一位置插入使得费用增加的最少,将所有点插入后即为最优解。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 5e3 + 5;
const int MOD = 1e9 + 7;
const int inf = (1 << 31) - 1;
const ll INF = 1ll << 60;



ll n, s, e;
ll q1, q2, q3, q4, q5;
ll x[MAXN], a[MAXN], b[MAXN], c[MAXN], d[MAXN];
ll cost[MAXN][MAXN];
ll Next[MAXN];

inline ll jump(int i, int j) {
    return  abs(x[i] - x[j]) + (i > j ? (c[i] + b[j]) : (d[i] + a[j]));
}

inline void update(int num) {
    q1 = s;
    q4 = INF;
    while (Next[q1] != 0) {
        if (-cost[q1][Next[q1]] + cost[q1][num] + cost[num][Next[q1]] < q4) {
            q2 = q1;
            q4 = -cost[q1][Next[q1]] + cost[q1][num] + cost[num][Next[q1]];
        }
        q1 = Next[q1];
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> s >> e;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) cin >> d[i];
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cost[i][j] = jump(i, j);
            cost[j][i] = jump(j, i);
        }
    }
    Next[s] = e;
    for (int j = 1; j <= n; j++) {
        if (!Next[j] && j != e) {
            update(j);
            Next[j] = Next[q2];
            Next[q2] = j;
        }
    }
    ll ans(0);
    q1 = s;
    while (Next[q1]) {
        ans += cost[q1][Next[q1]];
        q1 = Next[q1];
    }
    cout << ans << endl;
}

标签: graphs, dp, greedy

添加新评论