lessons/参考实现/05-最短路与类最短路/CodeForces-1340C.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int road_length, m;
    cin >> road_length >> m;
    vector<int> position(m);
    for (int &x : position) cin >> x;
    sort(position.begin(), position.end());
    int green, red;
    cin >> green >> red;

    const int INF = numeric_limits<int>::max() / 4;
    vector<int> distance(m * green, INF);
    auto id = [green](int island, int spent) { return island * green + spent; };
    int start = lower_bound(position.begin(), position.end(), 0) - position.begin();
    deque<pair<int, int>> queue;
    distance[id(start, 0)] = 0;
    queue.push_back({start, 0});
    long long answer = numeric_limits<long long>::max();

    while (!queue.empty()) {
        auto [island, spent] = queue.front();
        queue.pop_front();
        int completed = distance[id(island, spent)];
        int to_finish = road_length - position[island];
        if (to_finish <= green - spent) {
            answer = min(answer, 1LL * completed * (green + red) + spent + to_finish);
        }
        for (int direction : {-1, 1}) {
            int next_island = island + direction;
            if (next_island < 0 || next_island >= m) continue;
            int next_spent = spent + abs(position[next_island] - position[island]);
            if (next_spent > green) continue;
            int add = (next_spent == green);
            if (add) next_spent = 0;
            int state = id(next_island, next_spent);
            if (completed + add >= distance[state]) continue;
            distance[state] = completed + add;
            if (add) queue.push_back({next_island, next_spent});
            else queue.push_front({next_island, next_spent});
        }
    }
    if (answer == numeric_limits<long long>::max()) cout << -1 << '\n';
    else cout << answer << '\n';
    return 0;
}