| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 2084 | 523 | 338 | 21.245% |
문제
주환이는 요즘 등산에 빠졌다. 주환이는 등산을 위해 지도를 가지고 있는데, 그 지도에는 각 지점의 높이와 갈 수 있는 다른 지점까지의 거리가 표시되어 있다.
주환이는 아침에 집에서 출발하여 등산을 갔다가, 오후 수업을 듣기 위해 고려대학교로 돌아와야 한다.
A. 주환이는 지도의 임의의 지점을 골라, 그 지점을 목표로 정한다. 집 또는 고려대학교는 목표로 선택할 수 없다.
B. 주환이가 집에서 정한 목표에 도달할 때 까지는 항상 높이가 증가하는 방향으로만 이동해야 한다.
C. 주환이가 정한 목표에 도달한 후, 고려대학교로 갈 때에는 항상 높이가 감소하는 방향으로만 이동해야 한다.
D. 주환이는 거리 1을 움직일 때 마다 D 의 체력이 소모된다.
E. 주환이는 정한 목표에 도달하면 높이 1당 E 의 성취감을 얻는다. 즉 높이가 h인 목표에 도달하면 hE의 성취감을 얻는다.주환이는 이 등산의 가치를 (얻은 성취감) - (소모한 체력) 으로 계산하기로 하였다. 주환이를 위해 가치가 가장 높은 등산 경로를 선택해주자.
입력
첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000, 1 ≤ D ≤ 100, 1 ≤ E ≤ 100)
두 번째 줄에 N개의 정수 h1, ... ,hN이 공백으로 구분되어 주어진다. hi는 i 번째 지점의 높이를 의미한다. (1 ≤ hi ≤ 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에서부터 각 노드까지의 거리, N에서부터 각 노드까지의 거리를 구하면 된다.
다만, 높이가 증가하는 방향으로만 갈 수 있게끔 구현해주면 된다.
거리를 구했으면, 2부터 N - 1까지 순회하면서 식을 넣어주면 된다.
물론, 1이나 N 두 위치 모두에서 갈 수 있는 곳만 계산해줘야 된다.
노드가 10만이고, 각 거리도 10만이라 int의 범위로는 불가능하다.
처음부터 long long을 썼어야 됐는데, 경솔했다.
풀이
1에서부터의 거리와 N에서부터의 거리를 from_1, from_N 배열에 담아줬다.
h[next] <= h[node] 처리만 빼면 일반 다익스트라 알고리즘과 동일하다.
성취도가 음수가 될 수 있으므로, ans의 초기 설정은 LLONG_MIN으로 해주어야 된다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N, M, D, E;
ll h[100001], ans = LLONG_MIN, from_1[100001], from_N[100001];
vector<pair<int, ll>> edge[100001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN2(N, M);
CIN2(D, E);
FUP(i, 1, N)
{
CIN(h[i]);
from_1[i] = from_N[i] = LLONG_MAX;
}
while (M--)
{
int u, v, w;
CIN3(u, v, w);
edge[u].push_back({ v, w });
edge[v].push_back({ u, w });
}
from_1[1] = from_N[N] = 0;
priority_queue<pair<ll, int>> pq;
pq.push({ 0, 1 });
while (!pq.empty())
{
int node = pq.top().second;
ll dist = -pq.top().first;
pq.pop();
if (from_1[node] < dist) continue;
for (auto p : edge[node])
{
ll nd = dist + p.second;
int next = p.first;
if (h[next] <= h[node] || from_1[next] <= nd) continue;
from_1[next] = nd;
pq.push({ -nd, next });
}
}
pq.push({ 0, N });
while (!pq.empty())
{
int node = pq.top().second;
ll dist = -pq.top().first;
pq.pop();
if (from_N[node] < dist) continue;
for (auto p : edge[node])
{
ll nd = dist + p.second;
int next = p.first;
if (h[next] <= h[node] || from_N[next] <= nd) continue;
from_N[next] = nd;
pq.push({ -nd, next });
}
}
FUP(i, 2, N - 1)
{
if (from_1[i] == LLONG_MAX || from_N[i] == LLONG_MAX) continue;
ans = max(ans, h[i] * E - (from_1[i] + from_N[i]) * D);
}
ans == LLONG_MIN ? COUT("Impossible") : COUT(ans);
return 0;
}