[백준 13308] 주유소 (C++)

13308번: 주유소

다익스트라, 다이나믹 프로그래밍

---

정점을 지나면서 지금까지 지나온 도시중 리터당 가격이 가장 싼 곳의 가격정보를 들고다니면 된다.

 

처음에 dist배열을 만들어주지 않고 전체 탐색을 하게해서 메모리초과를 띄웠다.

pq에 중복된값이 엄청많이 들어간다고 생각했고 걸러줄 방법이 필요했는데 dp를 사용했다.

 

현재 정점까지 이동한 비용의 최솟값을 저장하는데 현재 정점에서 가지고 있는 리터당 가격정보도 같이 저장해야한다.

dp[현재 정점][리터당 가격의 최솟값] = 비용의 합

 

dp배열을 설정해주고 pq에 정보를 입력하기 전에, 이번에 구한 '리터당 가격 최소'를 가지고 다음 정점을 방문한 적이 있다면 해당 정점을 pq에 넣을 필요가 없기 때문에 continue를 해준다.

 

그리고 dp배열을 초기화 해주면서 pq에 넣은게 아니기 때문에 현재 pq에 중복된 값이 있을 수 있다. 따라서 현재 리터당 가격을 가지고 현재 정점을 방문한적이 있다면 continue.

구한적이 없다면 현재 비용을 dist에 입력하고, 현재 정점이 N이라면 현재 비용을 출력하고 종료한다. 우선순위 큐를 사용하는 다익스트라알고리즘이기 때문에 N을 만나면 바로 리턴할 수 있다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define LINF 1e15
#define pii pair<int, int>
typedef long long ll;
#define pil pair<int ,ll>
// typedef pair<int, int> pii;
 
using namespace std;
 
struct INFO{
    int city;
    ll cost;
    int min_ppl; // price per liter
};
 
struct cmp{
    bool operator()(INFO &a, INFO &b){
        return a.cost > b.cost;
    }
};
 
int N, M;
int price[2501];
ll dist[2501][2501];
vector<pil > adj[2501];
 
void input(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        cin >> price[i];
    }
    int u, v, c;
    for(int i = 0; i < M; i++){
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    memset(dist, -1, sizeof(dist));
}
 
void solve(){
    ll res = LINF;
    priority_queue<INFO, vector<INFO>, cmp> pq;
    pq.push({1, 0, price[1]});
    
    while(!pq.empty()){
        int now = pq.top().city;
        ll now_cost = pq.top().cost;
        int now_ppl = pq.top().min_ppl;
        pq.pop();
        
        if(dist[now][now_ppl] != -1) continue;
        dist[now][now_ppl] = now_cost;
        
        if(now == N){
            cout << now_cost << "\n";
            return;
        }
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i].first;
            ll next_cost = now_cost + adj[now][i].second * now_ppl;
            int next_ppl = min(now_ppl, price[next]);
            
            if(dist[next][next_ppl] != -1) continue;
            pq.push({next, next_cost, next_ppl});
        }
    }
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}