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

www.acmicpc.net/problem/13308

13308번: 주유소

 

 

 

알고리즘 종류

다익스트라

DP

 

 

 

사고 과정

이 문제는 노드에 비용과 간선의 거리가 존재합니다. 이 2가지를 고려해야 합니다.

 

이 문제를 간단하게 생각해 보겠습니다. 노드가 그물형으로 연결된 것이 아닌 선형으로 연결되어 있다고 가정하겠습니다. 상태가 아래와 같을 때, 1번노드에서 2번 노드로 가는 비용은 20 * 거리가 됩니다.

 

이제 2번 노드에서 3번으로 가겠습니다. 비용 30과 비교했을 때, 여전히 20가 낮은 비용이므로 20을 선택합니다.

 

이제 3번 노드에서 4번으로 가겠습니다. 이전의 비용 20보다 3번 노드의 비용 10이 더 저렴합니다. 따라서 10을 선택합니다.

 

이런 식으로 i번 노드에서 j번 노드로 비용 k를 가지고 가는 최종 최소 비용을 구하면 됩니다. 그래서 DP를 2차원 배열로 만들겠습니다.

 

costs[j][k] : 1번 노드에서 j번 노드로 비용 k를 가지고 갈 때의 최종 최소 비용.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#define INF 1e15
 
using namespace std;
 
typedef long long ll;
 
int n, m;
 
int prices[2501];
ll costs[2501][2501]; // 1에서 j까지 기름값 k로 가는 비용  
vector<vector<pair<int, int> > > edges;
 
 
ll dijkstra(){
    
    for(int i=0; i<=n; i++){
        for(int j=0; j<=2500; j++){
            costs[i][j] = INF;
        }
    }
    
    priority_queue<pair<ll, pair<int, int> > > pq; // cost, node, gas price
    pq.push({0, {1, prices[1]}});
    
    while(!pq.empty()){
        int node = pq.top().second.first;
        ll cost = -pq.top().first;
        int price = pq.top().second.second;
        pq.pop();
        
        if(costs[node][price] < cost) continue;
        if(node == n) return cost; // 목적지에 도달했으면 종료. 우선순위 큐를 이용했기 때문에 최소 비용이 된다. 
        
        for(int i=0; i<edges[node].size(); i++){
            int next_node = edges[node][i].first;
            ll next_cost = cost + edges[node][i].second * price;
            int next_price = min(price, prices[next_node]);
            
            if(costs[next_node][price] > next_cost){
                costs[next_node][price] = next_cost;
                pq.push({-next_cost, {next_node, next_price}});
            }
        }
    }
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    edges.resize(n+1); 
    
    for(int i=1; i<=n; i++){
        cin >> prices[i];
    }
    
    int a, b, c;
    for(int i=0; i<m; i++){
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    
    cout << dijkstra();
}

 

 

 

시행착오