[백준]주유소(13308)

문제 링크 : [백준]주유소(13308)

문제 설명

N개의 도시가 있고, 각 도시에는 주유소가 있고 각 주유소마다 기름값이 주어집니다.
도시간 도로의 거리가 주어졌을 때, 1번 도시에서 출발하여, N번 도시에 도착하기 위한 최소 기름값을 구하세요.

입력

N(도시 갯수, 1 <= N <= 2,500)
M(도로의 갯수, 1 <= M <= 4,000)
O_i(각 도시의 기름값, 1 <= O_i <= 2,500)
S_i E_i D_i(출발 도시, 도착 도시, 도시간 거리, 1 <= D_i <= 2,500)

4 4
5 2 4 1
3 1 3
1 2 2
4 3 4
2 4 15

출력

28

카테고리

#다익스트라 #DP

시간 복잡도 상한

O(N * M * logM)

해결 방법

1. 얼핏 보면 단순 다익스트라처럼 보입니다.
2. 하지만 비용을 구하는 방식이 단순 엣지의 비용이 아닌, 엣지 비용 * 기름값으로 비용을 구하는 방식이 다릅니다.
3. 정확하게 비용을 구하는 방식은, [현재까지 비용 + 현재까지 방문한 도시들의 기름값 중 최소값 * 다음 도시까지의 거리]가 됩니다.
4. 이 내용을 우선순위 큐에 넣으면 될 것 같지만, 이렇게 하게되면, 예제에서 처럼 1번에서 2번을 방문하면서 최소 기름값이 변경되어 다시 돌아오는 경우를 처리할 수 없습니다.
   4-1. 이미 1번 노드의 최소비용은 0으로 책정되었기 때문에, 일반적인 다익스트라에서는 다음에 더 큰 비용이 오기 때문에 무시됩니다.
5. 그렇다고 이미 책정된 최소비용을 무시하고 계속 간선 정보들을 넣다보면 TLE가 발생합니다.
6. 현재 노드에 방문하는 최소 비용을 노드 번호와 지금까지의 최소기름값을 가지고 관리하게 합니다.
7. 따라서 이미 방문한 노드라도 더 작은 최소 기름값으로 왔다면 정보를 추가하여 다익스트라를 진행합니다.
8. 그 이후에는 N번 노드가 나올 때까지 다익스트라를 돌리면 됩니다.

시간복잡도

O(N * M * logM)

코드

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#define sf second.first
#define ss second.second
#define M 999999999999
using namespace std;
typedef pair<int,int>P;
typedef long long L;
int n,m,o[2501],i,j,a,b,c;
vector<P>v[2501];
priority_queue<pair<L,P>,vector<pair<L,P>>,greater<pair<L,P>>>q;
bool d[2501][2501];
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",o+i);
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    q.push({0,{1,o[1]}});
    while(!q.empty()){
        pair<L,P>x=q.top();q.pop();
        if(d[x.sf][x.ss])continue;
        if(x.sf==n){
            printf("%lld",x.first);
            break;
        }
        d[x.sf][x.ss]=x.first;
        for(P y:v[x.sf]){
            if(d[y.first][min(x.ss,o[y.first])])continue;
            q.push({x.first+x.ss*y.second,{y.first,min(x.ss,o[y.first])}});
        }
    }
}