백준 13308 : 주유소 (다익스트라, DP)

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

13308번: 주유소

풀이
2차원 다익스트라 문제
1번부터 N번까지의 경로 중 현재 방문한 정점 기준으로 이전에 방문한 정점들 중 가장 리터당 금액이 작은 것을 선택하여 구매를 하는 것이 이득이다. 경로를 탐색할 때 가장 작은 리터당 금액을 기록하면서 탐색한다.
DP[i][j] : 리터당 최소값이 j일 때 1부터 i까지 갈 수 있는 최소비용
우선순위큐를 사용했기 때문에 N번 정점에 방문하는 순간이 최적해가 된다.

#include<bits/stdc++.h>
#include<time.h>


#define MAX 5000001
#define INF 200000000000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { -1, 0, 1, 0, 1, 1, -1, -1 };
int dy[8] = { 0, 1, 0, -1, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }


int n, m;
ll literPrice[2501];
vector<pll> graph[2501];
vector<vector<ll>> dp(2501, vector<ll>(2501, INF));

ll func(int start,int end) {
    ll answer = INF;
    priority_queue<pair<ll,pll>> pq;

    pq.push({ 0,{-literPrice[start],start} });
    dp[start][literPrice[start]] = 0;

    while (!pq.empty()) {
        ll x = pq.top().second.second;
        ll mnPrice = -pq.top().second.first;
        ll price = -pq.top().first;
        pq.pop();
        if (x == end)
            return price;

        if (price > dp[x][mnPrice])
            continue;

        for (pll& next : graph[x]) {
            ll nx = next.first;
            ll nextMn = min(mnPrice, literPrice[x]);
            ll nextPrice = price + next.second * nextMn;
            if (dp[nx][nextMn] > nextPrice) {
                dp[nx][nextMn] = nextPrice;
                pq.push({ -nextPrice,{-min(literPrice[nx],nextMn),nx} });
            }
        }
    }

    return 0;
}
int main() {
    init();
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> literPrice[i];
    }
    for (int i = 0; i < m; i++) {
        int x, y, z; cin >> x >> y >> z;
        graph[x].push_back({ y,z });
        graph[y].push_back({ x,z });
    }

    cout << func(1, n);
}