[백준 13308 - C++] 주유소 : 다익스트라(Dijkstra)

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

13308번: 주유소

문제

어떤 나라에는 N개의 도시가 있고, 각 도시는 1번부터 N번까지 번호가 붙어 있다. 또, 서로 다른 두 도시를 양방향으로 직접 연결하는 M개의 도로가 있다. 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

1번 도시에서 N번 도시로 자동차를 이용하여 이동하려고 한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시와 4개의 도로가 있다고 하자. 원 안에 있는 숫자는 도시의 번호, 원 옆에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 옆에 있는 숫자는 도로의 길이를 표시한 것이다. 

1번 도시에서 출발할 때 7리터의 기름을 넣고 그 기름으로 4번 도시까지 (3번 도시를 거쳐) 이동하면 총 비용은 35원이다. 만약 1번 도시에서 출발할 때 3리터의 기름을 넣고(3×5 = 15원) 3번 도시로 이동한 다음, 다시 3번 도시에서 4리터의 기름을 넣고(4×4 = 16원) 4번 도시에 도착하면 총 비용은 31원이다. 또 다른 방법으로 1번 도시에서 2리터의 기름을 넣고(2×5 = 10원) 2번 도시로 이동하여, 2번 도시에서 9리터의 기름을 넣고(9×2 = 18원) 1번과 3번 도시를 거쳐 4번 도시에 도착하면 총 비용은 28원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도로들의 길이를 입력으로 받아 1번 도시에서 N번 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도시 번호 순서대로 N개의 자연수로 주어진다. 리터당 가격은 1 이상 2,500 이하의 자연수이다. 그 다음 M개의 줄 각각에 하나의 도로에 대한 정보가 세 개의 자연수로 주어지는데, 처음 두 개의 자연수는 도로가 연결하는 두 도시의 번호이며, 세 번째 자연수는 도로의 길이이다. 도로의 길이는 1 이상 2,500 이하의 자연수이다. 한 쌍의 도시를 연결하는 도로는 최대 하나만 존재한다. 임의의 도시에서 다른 임의의 도시로 도로들을 이용하여 이동할 수 있는 방법이 항상 존재한다. 

출력

표준 출력으로 1번 도시에서 N번 도시로 가는 최소 비용을 출력한다.

 

풀이

이 문제는 다익스트라와 dp를 함께 사용해야 하는 문제이다.

이 때 중요한 것은 dp[][]의 값이 처음 변하는 경우만 고려해야 한다는 것이다. 또 볼 필요가 없는 것은 다익스트라에서 다음에 방문하면 무조건 더 멀리 돌아온 경우에 해당하기 때문이다. 처음엔 이를 이용하지 못해서 계속 다시 방문을 하게 코드를 짜서 60퍼쯤에서 계속 시간초과가 났다ㅠㅠ

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

long long int dp[2501][2501];
int oil[2501];
int n, m;

vector <pair<int, int>> way[2501];
priority_queue<pair<long long int, pair<int, int>>> pq;     //cost, pos, oil price

void dijkstra(){
    int here, there, here_o, there_o;
    long long int here_c, there_c;
    long long int min_c;

    for(int i=0; i<=n; i++)
        for(int j=0; j<2501; j++)
            dp[i][j] = -1;
    pq.push(make_pair(0, make_pair(1, oil[1])));
    
    while(!pq.empty()){
        here = pq.top().second.first;
        here_c = -pq.top().first;           //here까지 비용
        here_o = pq.top().second.second;    //here까지의 최소 오일값
        pq.pop();
        
        if(dp[here][here_o] != -1)
            continue;
        
        dp[here][here_o] = here_c;
        
        if(here == n){      //도착!
            min_c = here_c;
            //printf("!!%d\n", n);
            break;
        }
        for(int i=0; i<way[here].size(); i++){
            there = way[here][i].first;
            there_c = way[here][i].second * min(here_o, oil[here]) + here_c;    //there까지 비용
            there_o = min(here_o, oil[here]);               //이번 이동에 쓰인 오일 값
            
            
            if(dp[there][there_o] == -1 ){
                pq.push(make_pair(-there_c, make_pair(there, there_o)));
            }
        }
        
    }
    
    printf("%lld\n", min_c);
}

int main(void) {
    int a, b, cost;
    
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%d", &oil[i]);
    }
    for(int i=0; i<m; i++){
        scanf("%d %d %d", &a, &b, &cost);
        way[a].push_back(make_pair(b, cost));
        way[b].push_back(make_pair(a, cost));
    }
    dijkstra();
}