백준 13305번 주유소

https://www.acmicpc.net/problem/13305

13305번: 주유소

어떤 주유소의 가격이 가장 싸다면 그 주유소에서 목적지까지 갈 기름을 전부 사는것이 이득이다.

우선순위 큐를 이용하여 각 주유소의 비용이 적은 순으로 정렬하고 각 주유소부터 자신 이전에 찾은(더 비용이 적은) 주유소가 나올 때 까지 갈 수 있는 기름을 사도록 코드를 짰다.

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    /*
    fist : 우선순위 큐에서 나ㅏ온 원소에 대해 자신보다 더 싼 주유소가 가장 처음 나오는 위치
    nowcost : 마지막에 비용을 계산할 때 현재 확인중인 도로를 지나가기 위한 기름을 살때 드는 리터당 가격
	*/
    int N, fisr = 100000, nowcost;
	long long int ans = 0;
    //거리가 최대 1000000000km, 도로는 999999999개, 리터당 가격도 최대 1000000000이니 long long int를 사용해야 한다
	cin >> N;
    //pair의 first는 비용 * -1, second는 도시 번호
	priority_queue<pair<int, int>> que;
    //calculating : 해당 지점에서 기름을 살지 말지를 저장하는 벡터
	vector<int> distandd(N - 1), cost(N), calculating(N);
	for (int i = 0; i < N - 1; i++){
		cin >> distandd[i];
	}
	for (int i = 0; i < N; i++){
		cin >> cost[i];
		que.push({ -cost[i], i });
	}

	while (!que.empty()){
		pair<int, int> a = que.top();
		que.pop();
		if (fisr < a.second) continue;
		fisr = a.second;
		calculating[a.second] = -a.first;
	}

	for (int i = 0; i < N; i++){
		if (calculating[i]) nowcost = calculating[i];
		if (i < N - 1) ans += (long long int) nowcost * distandd[i];
	}

	cout << ans;

	return 0;
}