Notice
Recent Posts
Recent Comments
Link
알고리즘 모음(C++)
백준 13308 - 주유소(C++) 본문
문제 링크입니다. https://www.acmicpc.net/problem/13308
다익스트라와 다이나믹 프로그래밍이 사용된 문제였습니다.
이 문제는 1번부터 N번점까지 이동할 때, 필요한 최소 비용을 구하는 문제입니다.
이전에 지났던 점을 다시 지날 수 있으며, 기름을 싼 곳에서 전부 채워온 후 한번에 이동할 수 있기에
어느 정점에서, 어떤 기름값으로 채웠을 때 드는 최소 비용을 저장해줘야 했습니다.
따라서, 값을 저장해주는 배열을 ‘위치+기름값’ 인 2차원 배열로 구성해줘야했습니다.
그리고, 어떤 정점을 지날 때의 기름 값을 최소로 저장해줘야 했습니다.
그래야지 지나는 곳에서 가장 싼 기름 값으로 가득 채워서 이동한다고 구할 수 있기 때문입니다.
-> queue에 값을 넣을 때, 최소 비용과 위치 뿐만 아닌, 지금까지의 최소 기름 값을 함께 넣어줘서 탐색할 때마다 최소 기름값을 갱신하며 구할 수 있도록 해줬습니다.
자세한 것은 코드를 참고해주세요.
#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF LLONG_MAX
#define F first
#define S second
using namespace std;
int N, M;
int cost_oil[2501];
vector<pair<int, int>> connect[2501];
long long Distance[2501][2501]; // 위치 + 최소 오일
priority_queue<pair<long long, pair<int, int>>> q; //비용, 위치, 오일 가격
long long ans = INF;
void reset_distance(){
for(int i = 0; i <= N; i++){
for(int j = 0; j <= 2500; j++){
Distance[i][j] = INF;
}
}
}
void Dijstra(){
q.push({-0, {1, cost_oil[1]}});
while(!q.empty()){
int x = q.top().S.F; // 현재 위치
int oil = q.top().S.S; // 현재까지 오일의 최소 값
long long cost = -q.top().F; // 지금까지 최소 비용
q.pop();
if(x == N && ans > cost) ans = cost;
if(Distance[x][oil] < cost) continue; // 현재 탐색할 경우가 이전보다 클 경우 탐색할 필요가 없음
for(int i = 0; i < connect[x].size(); i++){
int xx = connect[x][i].F;
long long n_cost = cost + connect[x][i].S * min(oil, cost_oil[x]); // 지금까지 저장된 오일 값과 현재 위치의 오일값을 비교
int n_oil = min(cost_oil[x], oil); // 더 작은 값을 들고온다.
// xx의 값으로 비교하지 않는 이유는 아직 도착하지 않은 곳의 비용을 사용할 수 없기 때문
if(Distance[xx][n_oil] > n_cost){
Distance[xx][n_oil] = n_cost;
q.push({-n_cost, {xx, n_oil}});
}
}
}
}
void solve(){
reset_distance();
Dijstra();
cout << ans;
}
int main() {
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i = 1; i <= N; i++) scanf("%d", &cost_oil[i]);
for(int i = 1; i <= M; i++){
int x, y, cost;
scanf("%d %d %d", &x, &y, &cost);
connect[x].push_back({y, cost});
connect[y].push_back({x, cost});
}
solve();
return 0;
}
질문 및 조언은 댓글을 남겨주세요.
'백준' 카테고리의 다른 글
백준 6603 - 로또(C++) (0) | 2024.01.21 |
---|---|
백준 13907 - 세금(C++) (0) | 2024.01.05 |
백준 17835 - 면접보는 승범이네(C++) (0) | 2023.12.31 |
백준 1445 - 일요일 아침의 데이트(C++) (2) | 2023.12.30 |
백준 1486 - 등산(C++) (1) | 2023.12.23 |