백준 16681번 풀이

#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
#include <list>
#include <stack>
#define MAX 987654321

using namespace std;


class ClimbManager {
public:

    ClimbManager(long long n, long long d, long long e) {
        this->n = n;
        this->d = d;
        this->e = e;
        this->heights = new long long[n];
        this->buffer = new vector<pair<long long, long long>>[n];
        this->mountainBuffer = new vector<pair<long long, long long>>[n];
        this->univercityBuffer = new vector<pair<long long, long long>>[n];
    }

    void setHeight(long long index, long long height) {
        this->heights[index] = height;
    }

    void setRoute(long long from, long long to, long long distance) {
        this->buffer[from].push_back(make_pair(to, distance));
        this->buffer[to].push_back(make_pair(from, distance));
        auto fromHeight = this->heights[from];
        auto toHeight = this->heights[to];
        if (fromHeight < toHeight) {
            this->mountainBuffer[from].push_back(make_pair(to, distance));

            this->univercityBuffer[to].push_back(make_pair(from, distance));
        }
        if (toHeight < fromHeight) {
            this->mountainBuffer[to].push_back(make_pair(from, distance));

            this->univercityBuffer[from].push_back(make_pair(to, distance));
        }
    }


    vector<long long> printRouteToMountain(){
        return dijkstra(0, mountainBuffer);
    }

    vector<long long> printRouteToUnivercity() {
        return dijkstra(n-1, mountainBuffer);
    }



    void solution() {
        auto toMountain = this->printRouteToMountain();
        auto toUniversity = this->printRouteToUnivercity();
        long long value = LONG_LONG_MIN;
        bool hasRoute = false;
        for (auto i=1; i<n-1; i++) {
            if (toMountain[i] == -1 || toUniversity[i] == -1) {
                continue;
            }
            hasRoute = true;
            long long currentValue = e * this->heights[i] -d * (toMountain[i] + toUniversity[i]);
            value = max(value, currentValue);

        }
        if (hasRoute) {
            cout << value;
        } else {
            cout << "Impossible";
        }
//        return value;
//        return 0;
    }

private:
    long long n;
    long long d;
    long long e;
    long long * heights;
    vector<pair<long long, long long>> *buffer;

    vector<pair<long long, long long>> *mountainBuffer;
    vector<pair<long long, long long>> *univercityBuffer;

    vector<long long> dijkstra(long long index, vector<pair<long long, long long>> *aBuffer) {
        vector<long long> distances(n, -1);
//        distances[index] = 0;
        priority_queue<pair<long long, long long>> pq;

        pq.push({0, index});
        while (!pq.empty()) {
            auto top = pq.top();
            long long here = top.second;
            long long distance = -top.first;

            pq.pop();

            if (distances[here] != -1) {
                continue;
            }

            distances[here] = distance;

            for (auto it : aBuffer[here]) {
                long long next = it.first;
                long long acost = -it.second - distance;

                if (distances[next] != -1) {
                    continue;
                }
                pq.push(make_pair(acost, next));
            }

        }

//        for (auto i=0; i<n; i++) {
//            cout << distances[i] << ' ';
//        }
//
//        cout << '\n';
        return distances;
    }

};


int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


    long long n, m, d, e;
    cin >> n >> m >> d >> e;
    ClimbManager *manager = new ClimbManager(n, d, e);

    for (auto i=0; i<n; i++) {
        long long height;
        cin >> height;
        manager->setHeight(i, height);
    }

    for (auto i=0; i<m; i++) {
        long long a, b, d;
        cin >> a >> b >> d;
        a--; b--;
        manager->setRoute(a, b, d);
    }

//    manager->Aprlong longRouteToUnivercity();
//    manager->prlong longRouteToMountain();
//    manager->prlong longRouteToUniversity();
    manager->solution();
    return 0;
}