개요
-
입력
첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 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"을 쌍따옴표를 제외하고 출력한다. 답이 음수일 수 있음에 유의하여라.
접근방식
-
처음에 감을 아예 못 잡았다.
이 문제의 특성은 거리가 높아지는 방식으로 목표지점을 가고, 목표지점에서 학교까진 무조건 거리가 낮아지는 방식으로 가야하는 부분이다.
따라서 비교 값을 높이로 둔 우선순위 큐를 두개 생성해서 하나는 greater,
하나는 less 로 정렬해서 풀어보려했다. -
열심히 풀어봤지만 계속 의도치 않은 값만 나와서 디버깅을 해보던 중 깨달았다.
다익스트라의 기본원리는 우선순위 큐의 비교값을 지금까지 이동한 거리를 둬야 최단거리가 나오는 방식이다.
이렇게 높이를 비교값으로 놓아버리면 최단거리가 아니라 그냥 제일 촘촘히 올라가는 거리를 구할 뿐이였다
애초에 다익스트라에 대한 이해도가 없었던 접근방식이라고 생각한다. -
검색해본 결과, 목표지점까지 무조건 높이는 방향으로 올라가고,
목표지점에서 고려대학교까지 무조건 낮추는 방향으로 내려가는 부분을
쉽게 구현하는 방법은 간선값을 받을때 무조건 낮은곳에서 높은 곳의 방향으로 저장하는 것이다!//양방향 간선이므로 간선 정보를 받을 때, 무조건 낮은곳에서 높은곳으로 저장 for (int i = 0; i < M; i++) { cin >> tmpBeginNode >> tmpEndNode >> tmpDist; --tmpBeginNode; --tmpEndNode; if (Height[tmpBeginNode] < Height[tmpEndNode]) adj[tmpBeginNode].push_back({tmpEndNode,tmpDist}); if (Height[tmpBeginNode] > Height[tmpEndNode]) adj[tmpEndNode].push_back({ tmpBeginNode,tmpDist }); }무조건 낮은 위치에서 높은 위치로만 간선이 저장되므로
시작지점에서 모든노드로 다익스트라 돌리고,
고려대학교 지점에서 모든노드로 다익스트라를 돌려서
각노드마다 시작지점에서 해당 노드까지의 최단거리 + 고려대학교에서 해당 노드까지 최단거리값을 다 구해서 비교한 후 제일 큰 값이 답이 된다. -
처음엔 낮은위치에서 높은 위치로만 간선 저장하면
목표지점에서 고려대학교까지 높이를 낮추며 진행하는 부분은 어떻게 처리하나 의아했었다.
하지만 낮은곳에서 높은곳으로 간선을 저장을 하게되면 순방향 뿐만아니라 역방향에서도 낮은곳으로 높은곳으로 저장이되므로
저장 후 고려대학교에서 목표노드까지의 최단거리는
결국 고려대학교에서 목표노드까지 높이를 올리면서 올라간 거리가 되고
이 말은 목표노드에서 고려대학교까지 높이를 낮추면서 내려간 거리가 된다. -
모든 진행방향에서 조건을 만족 못하면 IMPOSSIBLE을 출력하는 방법도 사실 몰랐다.
이건 그냥 다익스트라 시작할 때 나올 수 없는 제일 큰 수 INF로 모든 배열을 초기화하고,
마지막에 시작점에서 노드i까지 최단거리+고려대학교에서 노드i까지 최단거리의 값들을 비교할때 각 최단거리가 INF보다 작을때만 진행하도록 하면 된다.//기본적으로 나올수없는 값인 -INF값을 Ans에 저장 long long Ans = -INF; //모든 노드를 순회하면서 출발점에서 해당노드 까지의 가치+ 고려대학교에서 해당 노드까지의 가치값중에 제일 큰 값을 저장 for (int i = 0; i < N; i++) { //목표노드까지의 최단거리가 INF 보단 작아야 한다! if (minDistFromEnd[i] < INF && minDistFromStart[i] < INF) Ans = max(Ans, (1LL * Height[i] * E - (minDistFromEnd[i] + minDistFromStart[i]) * D)); } //만약 Ans가 갱신이 안되었다면조건을 만족하는 길이 없다는 뜻이므로 IMpossible 출력 if (Ans == -INF) cout << "Impossible"; else cout << Ans;
전체코드
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<functional>
//일단 문제 이해 잘못이해 각 움직임마다 해당 높이*E- 거리*d연산이 아니라 마지막에 해당 목표의 높이*E- 이동한 전체거리*D이다.
//두번째는 높이를 기준으로 다익스트라를 사용하기 위해, pq의 first값을 높이값으로 잡아서 높이가 작은값을 기준으로 이동했는데, 값이 엄청 컸다
//높이를 높은쪽으로만 움직이는 방식은, adj벡터에 저장을 할때 높이를 낮은쪽에서 높은쪽으로 저장을 하면 끝이다.
using namespace std;
int N, M, D, E;
const long long INF = 1e18;
const int MAX = 100'000;
vector<vector<pair<long long, long long>>> adj;
int Height[100'001];
bool visited[100'001];
long long minDistFromStart[100'001];
long long minDistFromEnd[100'001];
//first는 각 정점의 높이, second는 정점의 인덱스
priority_queue < pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
void Input() {
int tmpBeginNode=0, tmpEndNode=0, tmpDist=0;
cin >> N >> M >> D >> E;
for (int i = 0; i < N; i++) {
cin >> Height[i];
}
fill(minDistFromEnd, minDistFromEnd + 100'000, INF);
fill(minDistFromStart, minDistFromStart + 100'000, INF);
adj.resize(MAX);
//양방향 간선이므로 간선 정보를 받을 때, 무조건 낮은곳에서 높은곳으로 저장
for (int i = 0; i < M; i++) {
cin >> tmpBeginNode >> tmpEndNode >> tmpDist;
--tmpBeginNode;
--tmpEndNode;
if (Height[tmpBeginNode] < Height[tmpEndNode]) adj[tmpBeginNode].push_back({tmpEndNode,tmpDist});
if (Height[tmpBeginNode] > Height[tmpEndNode]) adj[tmpEndNode].push_back({ tmpBeginNode,tmpDist });
}
}
void Solution() {
//출발점정보 우선순위큐에 저장
minDistFromStart[0] = 0;
pq.push({ 0,0 });
fill(visited, visited + MAX, false);
//출발점에서 모든 점들까지 다익스트라를 이용해 minDistFromStart채우기
while (!pq.empty()) {
int curNode = 0;
do {
curNode = pq.top().second;
pq.pop();
} while (!pq.empty() && visited[curNode]);
if (visited[curNode]) break;
visited[curNode] = true;
for (auto& p : adj[curNode]) {
int nextNode = p.first, nextDist = p.second;
if (minDistFromStart[nextNode] > minDistFromStart[curNode] + nextDist) {
minDistFromStart[nextNode] = minDistFromStart[curNode] + nextDist;
pq.push({ minDistFromStart[nextNode],nextNode });
}
}
}
//방문배열 초기화하고 고려대학교정보 우선순위큐에 저장
fill(visited, visited + MAX, false);
minDistFromEnd[N - 1] = 0;
pq.push({0,N-1});
//고려대학교에서 모든 점들까지 다익스트라를 이용해 minDistFromEnd채우기
while (!pq.empty()) {
int curNode = 0;
do {
curNode = pq.top().second;
pq.pop();
} while (!pq.empty() && visited[curNode]);
if (visited[curNode]) break;
visited[curNode] = true;
for (auto& p : adj[curNode]) {
int nextNode = p.first, nextDist = p.second;
if ( minDistFromEnd[nextNode] > minDistFromEnd[curNode] + nextDist) {
minDistFromEnd[nextNode] = minDistFromEnd[curNode] + nextDist;
pq.push({ minDistFromEnd[nextNode],nextNode });
}
}
}
//기본적으로 나올수없는 값인 -INF값을 Ans에 저장
long long Ans = -INF;
//모든 노드를 순회하면서 출발점에서 해당노드 까지의 가치+ 고려대학교에서 해당 노드까지의 가치값중에 제일 큰 값을 저장
for (int i = 0; i < N; i++) {
//목표노드까지의 최단거리가 INF 보단 작아야 한다!
if (minDistFromEnd[i] < INF && minDistFromStart[i] < INF)
Ans = max(Ans, (1LL * Height[i] * E - (minDistFromEnd[i] + minDistFromStart[i]) * D));
}
//만약 Ans가 갱신이 안되었다면조건을 만족하는 길이 없다는 뜻이므로 IMpossible 출력
if (Ans == -INF) cout << "Impossible";
else
cout << Ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Input();
Solution();
}문풀후생
너무 어이없는 실수로 시간을 거의 그냥 갖다 버렸다.
방문배열까지 써서 우선순위큐에서 해당 노드가 나오면 넘기는 방식으로
작성했으나 시간초과가 계속 뜬 것이다!!
뭐가 문제일까 하고 이풀이 저풀이 다 찾아봐도 비슷하게 풀어서 멘탈이 나가고 있었다.
며칠뒤 다시보니 visited[curNode]=true; 가아니라
visited[curNode] == true; 로 작성되어있었다.....
