문제 링크
문제
파댕이는 중견기업 회사에서 직장인으로 일하고 있다. 사장님이 직장인 파댕이를 무척 아끼기 때문에, 파댕이는 사장실에 찾아가 사장님께 인사를 하려고 한다.
직장인 파댕이의 회사가 있는 건물은 층으로 구성되어 있는데 각 층은 방과 복도로 구성되어 있다. 복도를 통해 방과 방 사이를 양방향으로 이동할 수 있다. 모든 층은 같은 모습을 하고 있다. 파댕이는 현재 1층의 1번 방에 있고, 사장실은 층의 번 방이다. 파댕이는 현재 자신의 위치에서부터 사장실까지 최소 시간을 사용하여 도착할 방법을 찾아야 한다.
파댕이는 각각의 복도를 지나가는 데 걸리는 시간이 얼마인지 알고 있다. 더불어 어떤 방에는 엘리베이터가 있어서 그 엘리베이터를 타고 위층으로 올라갈 수 있다. 한 층의 번 방에 설치된 엘리베이터는 다른 층에 있는 모든 번 방을 연결한다. 특정 엘리베이터에만 사람이 몰릴 수 있기 때문에 어떤 엘리베이터는 빠르고 어떤 엘리베이터는 느릴 수 있다. 파댕이는 각각의 엘리베이터가 한 층을 올라가는 데 걸리는 시간이 얼마인지도 알고 있다.
건물의 모습과 엘리베이터의 속도가 주어지면, 파댕이가 사장실까지 가는 최소 시간을 계산하는 프로그램을 작성하시오.
입력
첫째 줄에 방의 수 N(2 ≤ N ≤ 100,000)과 복도의 수 M(1 ≤ M ≤ 300,000), 건물의 층수 K(2 ≤ K ≤ 200,000)가 공백으로 구분되어 주어진다.
다음 줄부터 개의 줄에 걸쳐 세 정수 가 공백으로 구분되어 주어진다. (1 ≤ u, v ≤ N, 1 ≤ c ≤ 100,000,000, u ≠ v)
이는 번 방과 번 방을 잇는 복도가 존재하며 이를 지나가는 데 걸리는 시간이 라는 뜻이다.
임의의 서로 다른 두 방에 대해 한쪽 방에서 다른 쪽 방으로 이어진 복도는 1개 이하다.
다음 줄에 개의 정수 e1, ⋯ 이 공백으로 구분되어 주어진다. (ei = −1 or 1 ≤ ei ≤ 100,000,000)
이는 번째 방에 존재하는 엘리베이터를 타면 한 층을 올라갈 때마다 의 시간이 든다는 뜻이다. 만약 번째 방에 엘리베이터가 존재하지 않는다면, 이다.
출력
파댕이가 사장실까지 가는 최소 시간을 출력한다. 만약 파댕이가 사장실에 도달할 수 없다면 을 출력한다.
예제 입력 1
5 7 4
1 2 7
1 3 11
1 4 7
2 3 13
2 4 4
2 5 16
4 5 10
3 -1 1 3 -1
예제 출력 1
26
예제 입력 2
3 2 7
1 2 3
2 3 8
-1 -1 -1
예제 출력 2
-1
알고리즘 분류
- 최단 거리 알고리즘
풀이
무조건 시간이 적게 걸리는 엘리베이터를 가진 방을 고르는 게 아니라, 해당 방을 거치는 경로가 N번 방까지 가장 빨리 도달하는지까지를 따져야 한다.
먼저 1번 방에서 2~N번 방까지 도달하는 데 걸리는 시간과, N번 방에서 1~N-1번 방까지 도달하는 데 걸리는 시간을 각각 기록해두며, 이 때 총 2번의 데이크스트라를 수행하게 된다.
그리고 엘리베이터가 없는 방을 제외하고, 1번 방에서 A번 방까지 도달하는 데 걸리는 시간 + 1층에서 K층까지 A번 방에서 엘리베이터를 타고 도달하는 시간 + A번 방에서 N번 방까지 도달하는 데 걸리는 시간의 최솟값을 구한다.
만약 이 방법으로 N번 방까지 도달할 수 없다면 -1을 출력한다.
코드
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 100001
#define INF 9e15
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
using namespace std;
LL N, M, K, U, V, C;
vector<pair<LL, LL> > Edge[MAX];
LL E[MAX];
LL Dist[2][MAX];
LL Answer = INF;
void input() {
cin >> N >> M >> K;
for (int i = 0; i < M; i++) {
cin >> U >> V >> C;
Edge[U].push_back(make_pair(V, C));
Edge[V].push_back(make_pair(U, C));
}
for (int i = 1; i <= N; i++) {
cin >> E[i];
Dist[0][i] = INF;
Dist[1][i] = INF;
}
Dist[0][1] = 0;
Dist[1][N] = 0;
}
void dijkstra(int From, int Start) {
priority_queue<pair<LL, LL> > PQ;
PQ.push(make_pair(0, Start));
while (!PQ.empty()) {
LL NowC = -PQ.top().first;
LL NowX = PQ.top().second;
PQ.pop();
if (Dist[From][NowX] < NowC) {
continue;
}
for (int i = 0; i < (int)Edge[NowX].size(); i++) {
LL NextC = Edge[NowX][i].second;
LL NextX = Edge[NowX][i].first;
if (Dist[From][NextX] > Dist[From][NowX] + NextC) {
Dist[From][NextX] = Dist[From][NowX] + NextC;
PQ.push(make_pair(-Dist[From][NextX], NextX));
}
}
};
}
void settings() {
dijkstra(0, 1);
dijkstra(1, N);
for (int i = 1; i <= N; i++) {
if (E[i] == -1) {
continue;
}
Answer = min(Answer, Dist[0][i] + Dist[1][i] + (E[i] * (K - 1)));
}
}
void find_Answer() {
if (Answer == INF) {
cout << "-1\n";
}
else {
cout << Answer << "\n";
}
}
int main() {
FASTIO
input();
settings();
find_Answer();
return 0;
}
'BOJ > Gold' 카테고리의 다른 글
[BOJ/Gold 5] 백준 30470 호반우가 학교에 지각한 이유 3(C++) (1) | 2024.01.15 |
---|---|
[BOJ/Gold 3] 백준 29618 미술 시간(C++) (2) | 2024.01.12 |
[BOJ/Gold 4] 백준 30974 What's your ETA?(C++) (4) | 2024.01.10 |
[BOJ/Gold 4] 백준 30024 옥수수밭(C++) (1) | 2023.10.21 |
[BOJ/Gold 5] 백준 29792 규칙적인 보스돌이(C++) (1) | 2023.10.21 |