ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 16681번 풀이
    백준 2019. 12. 1. 21:05
    #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;
    }

    '백준' 카테고리의 다른 글

    백준 13460번 C++ 코드  (0) 2020.01.15
    백준 17370번 풀이  (0) 2019.12.03
    PS(알고리즘) 오픈 톡방 신입부원 대 모집!!  (0) 2019.12.01
    백준 14619번 c++ 풀이  (0) 2019.11.24
    백준 14612번 C++ 풀이  (0) 2019.11.21

    댓글 0

Designed by Tistory.