등산

https://www.acmicpc.net/problem/16681

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	3180	827	568	22.576%

문제

주환이는 요즘 등산에 빠졌다. 주환이는 등산을 위해 지도를 가지고 있는데,

그 지도에는 각 지점의 높이와 갈 수 있는 다른 지점까지의 거리가 표시되어 있다.

주환이는 아침에 집에서 출발하여 등산을 갔다가, 오후 수업을 듣기 위해 고려대학교로 돌아와야 한다.

1. 주환이는 지도의 임의의 지점을 골라, 그 지점을 목표로 정한다. 집 또는 고려대학교는 목표로 선택할 수 없다.

2. 주환이가 집에서 정한 목표에 도달할 때 까지는 항상 높이가 증가하는 방향으로만 이동해야 한다.

3. 주환이가 정한 목표에 도달한 후, 고려대학교로 갈 때에는 항상 높이가 감소하는 방향으로만 이동해야 한다.

4. 주환이는 거리 1을 움직일 때 마다 D 의 체력이 소모된다.

5. 주환이는 정한 목표에 도달하면 높이 1당 E 의 성취감을 얻는다. 즉 높이가 h인 목표에 도달하면 hE의 성취감을 얻는다.

주환이는 이 등산의 가치를 (얻은 성취감) – (소모한 체력) 으로 계산하기로 하였다.

주환이를 위해 가치가 가장 높은 등산 경로를 선택해주자.

입력

첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량,

높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다.

(2 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000, 1 ≤ D ≤ 100, 1 ≤  E ≤ 100)

두 번째 줄에 N개의 정수 h₁, …  ,h_N이 공백으로 구분되어 주어진다. h_i는 i 번째 지점의 높이를 의미한다.

(1 ≤ h_i ≤ 1,000,000, 1 ≤ i ≤ N)

세 번째 줄부터 M개의 줄에 걸쳐 세 정수 a, b, n이 공백으로 구분되어 주어진다.

이는 a번 지점과 b번 지점을 잇는 거리 n의 양방향 경로가 있음을 의미한다. (1 ≤ a, b ≤ N, 1 ≤ n ≤ 100,000)

어떤 지점에서 다른 지점으로 가는 경로가 여러 개 있을 수도 있으며 (등산로는 여러 개가 있을 수 있다),

한 지점에서 출발해 그 지점으로 돌아가는 경로가 있을 수도 있다 (쉼터에서 몇 바퀴 돌며 쉴 수도 있다).

주환이의 집은 1번 지점에 위치하고, 고려대학교는 N번 지점에 위치하며 주환이의 집과 고려대학교의 높이는 1임이 보장된다.

출력

첫 번째 줄에 주환이가 얻을 수 있는 가치의 최댓값을 출력한다.

만약 조건을 만족하는 등산 경로를 선택할 수 없다면, “Impossible“을 쌍따옴표를 제외하고 출력한다.

답이 음수일 수 있음에 유의하여라.

예제 입력 1

8 13 4 9
1 4 7 3 10 2 15 1
1 2 3
3 4 2
5 6 6
7 8 2
2 3 4
6 7 2
3 6 1
4 8 3
5 1 6
8 3 5
2 5 4
4 6 3
5 3 8

예제 출력 1

15

예제 입력 2

3 2 1 1
1 1 1
1 2 5
2 3 5

예제 출력 2

Impossible

출처

University > 고려대학교 > 2018 고려대학교 프로그래밍 경시대회 (KCPC) > Advanced Div. C번

University > 고려대학교 > 2018 고려대학교 프로그래밍 경시대회 (KCPC) > Intermediate Div. E번

• 문제를 만든 사람: oree2113

알고리즘 분류

• 그래프 이론
• 데이크스트라

---

통과된 코드

자료형 long long 필수!

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

constexpr int MAXN = 100001;
constexpr long long int INF = INT64_MAX;
constexpr long long int uINF = INT64_MIN;

///*
//각 노드에 연결되어 있는 노드에 대한 정보를 담는 벡터
//a번 노드에서 b번 노드로 가는 비용이 c라는 의미
//graph[a].push_back((make_pair(B, C));
//*/
vector<pair<int, int>> upGraph[MAXN];
vector<pair<int, int>> downGraph[MAXN];

// Dijkstra 알고리즘에 사용할 우선순위 큐
priority_queue<pair<long long int, int>> myPQ;

// N 지점의 개수, M 지점을 잇는 경로의 개수
// D 주환이의 거리 비례 체력 소모량, E 높이 비례 성취감 획득량
int N, M, D, E;

// 각 지점의 높이를 저장하는 배열
int hArr[MAXN];

// 등산을 하는데 필요한 배열 (집 -> 산)
long long int upArr[MAXN];

long long int temp = 0;
// 결과를 저장
long long int result = uINF;

// 하산을 하는데 필요한 배열 (산 -> 고려대)
long long int downArr[MAXN];

// V1,2 지점, d : 지점 사이의 거리
int V1, V2, d;

void Dijkstra(int start, long long int arr[], vector<pair<int, int>> graph[])
{
    // 임시배열 초기화
    for (int i = 1; i <= N; i++) arr[i] = INF;
    // 우선순위 큐에 삽입.
    myPQ.push({ 0, start }); // < first : 거리 , second : 노드 인덱스 >
    arr[start] = 0;
    while (!myPQ.empty()) {
        // -를 붙이는 이유는 우선순위 큐를 이용하여 정렬하기 위함이다.
        // (최소힙으로 구현)
        long long int nCost = -myPQ.top().first;
        int now = myPQ.top().second;
        myPQ.pop();
        // 이미 담겨 있는 것보다 거리가 크면 넘어간다.
        if (arr[now] < nCost) continue;
        // 해당 노드에서 연결된 모든 경로를 확인
        for (int i = 0; i < graph[now].size(); i++) {
            // disSum = 임시 노드 + 현재 노드에서 i로가는 비용
            long long int disSum = nCost + graph[now][i].second;
            // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            if (disSum < arr[graph[now][i].first]) {
                // 임시 노드 업데이트
                arr[graph[now][i].first] = disSum;
                // 우선순위 큐에 (거리, 노드 인덱스) 푸시
                myPQ.push(make_pair(-disSum, graph[now][i].first));
            }
        }
    }
}


int main()
{
    ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
    // cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
    cin.tie(NULL);
    cout.tie(NULL);

    // 문제의 조건들을 입력 받는다.
    cin >> N >> M >> D >> E;

    // 각 지점의 높이를 입력 받는다.
    for (int i = 1; i <= N; i++) cin >> hArr[i];

    // 경로를 입력 받는다.
    for (int i = 0; i < M; i++) {

        cin >> V1 >> V2 >> d;

        // 높이가 같을 경우에는 생각하지 않는다.
        if (hArr[V1] > hArr[V2]) { // V1의 높이가 더 높을 경우
            upGraph[V2].push_back(make_pair(V1, d));
            downGraph[V2].push_back(make_pair(V1, d));
        }
        else if (hArr[V1] < hArr[V2]) { // V1의 높이가 더 낮은 경우
            upGraph[V1].push_back(make_pair(V2, d));
            downGraph[V1].push_back(make_pair(V2, d));
        }

    }

    Dijkstra(1, upArr, upGraph);
    Dijkstra(N, downArr, downGraph);

    for (int i = 1; i <= N; i++) {
        if (upArr[i] == INF || downArr[i] == INF) continue;
        temp = upArr[i] + downArr[i];
        result = max(result, hArr[i] * E - temp * D);
    }

    if (result == uINF) cout << "Impossible";
    else cout << result;
    
    return 0;
}

최악의 경우 예를 들어 N = 100,000 / M = 200,000 / h_i = i / 모든 경로 거리 1 / D = 1 / E = 100 이런 식이면

int 를 사용하면 터진다. ㅠㅠ

long long int 로 바꾸어주자

로직 문제로 오인해서 많이 틀렸다.