[BOJ] 13308 : 주유소

문제 링크

13308번: 주유소 (acmicpc.net)

13308번: 주유소

DP와 그래프탐색 중 다익스트라 알고리즘이 결합된 문제.

사실 DP보다는 다익스트라 알고리즘에 가까운 것같다.

풀이

처음에 원래 다익스트라 알고리즘 처럼 dist라는 1차원 배열을 만들어서 최소비용을 저장했다.

하지만 이렇게 되면 예제처럼

이러한 상황에서 dist[3] 에는 1->3 경로로 인해 15가 저장되어있고, 1 -> 2 -> 3 -> 4 로 가는 루트가 최소비용으로 4에 도달하는 경로이지만 1 ->2-> 3 경로로 3에 도달하게 되면 16의 비용이 드는데 기존에 저장된 값보다 크기때문에 탐색을 멈추게 된다.

그래서 단지 그 지점에 도착했을 때 최소비용만 비교하는 것이 아니라 기름의 값도 같이 비교를 해서 탐색을 계속할 것인지 중단할 것인지 판단해야했다.

dist 배열을 2차원으로 만들어서 dist[현재 노드][현재 기름 값] 으로 만들어서 총 비용과 기름값 두 가지를 기준으로 효율적인 경로를 탐색했다.

만약 새로운 경로의 총 비용이 기존 탐색된 경로보다 많아도 현재 기름값이 기존 경로보다 작다면 멀리봤을 때는 더 효율적인 경로가 될 수 있다는 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<ll, int>, int>, vector<pair<pair<ll, int>, int>>, greater<pair<pair<ll, int>, int>>> Priority_queue;
const ll INF = LLONG_MAX;
const int MAX_N = 2500 + 5;
int oil_price[MAX_N];
int N, M;
vector<pair<int, int>> Edge[MAX_N];
ll dist[MAX_N][MAX_N];
void dijkstra(int st, int ed);
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> oil_price[i];
    }
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        Edge[u].push_back({ v,w });
        Edge[v].push_back({ u,w });
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 2500; j++)
            dist[i][j] = INF;
    }
    dijkstra(1, N);
    return 0;
}
 
void dijkstra(int st, int ed) {
    //큐에 현재점, 여태 지나온 점 중에 기름이 가장 쌌던곳, 비용 이 들어있어야함
    Priority_queue pq;
    pq.push({ {0,st},oil_price[1] });
    while (!pq.empty()) {
        ll cost = pq.top().first.first;
        int now = pq.top().first.second;
        int price = pq.top().second;
        pq.pop();
        if (dist[now][price] < cost)
            continue;
        if (now == ed) {
            cout << cost << "\n";
            return;
        }
        for (int i = 0; i < Edge[now].size(); i++) {
            int next = Edge[now][i].first;
            int distance = Edge[now][i].second;
            ll acost = cost + (distance * price);
            if (dist[next][price] <= acost)
                continue;
            int min_price = min(price, oil_price[next]);
            dist[next][price] = acost;
            pq.push({ { acost,next }, min_price});
        }
    }
}