알고리즘 모음(C++)

백준 13308 - 주유소(C++) 본문

백준

백준 13308 - 주유소(C++)

공대생의 잡다한 사전 2024. 1. 3. 23:51

문제 링크입니다. https://www.acmicpc.net/problem/13308

13308번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도

www.acmicpc.net

다익스트라와 다이나믹 프로그래밍이 사용된 문제였습니다.


이 문제는 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