13308번 주유소

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

다익스트라 dijstra bfs 우선순위큐 복습 코딩테스트 추천 필수 boj 코테 생각 KCM Travel

아래 비슷한 문제도 풀어보자.

비슷한(?) 문제 : 

https://hsdevelopment.tistory.com/466

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

핵심은 visit 2차원 배열이고, bfs스럽게(?) dijstra를 구현하면 된다. 또한, 우선순위큐 내의 원소도 3개를 활용한다.

visit[a][b] : a는 현재 도시(a번 도시까지 왔다), b는 지금까지 거쳐간 도시들 중 가장 싼 주유소 리터당 값

그리고 total을 바로 return하는 이유는 우선순위큐이기 때문에 항상 최솟값을 보장한다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long
#define Max 2505
 
LL n, m, city[Max]; // city[i] : i번 도시의 주유소 리터당 값
bool visit[Max][Max]; // visit[a][b] : a번 도시까지 이동했을 때, 지금까지 거쳐간 가장 싼 주유소 기름값
vector<pair<int, LL> > v[Max];
 
LL dijstra(int s)
{
    // {총 비용, {다음 도시, 다음 도시까지의 거리}}
    priority_queue<pair<LL, pair<int, LL> > > pq;
    pq.push({ 0, {s, city[s]} }); // 출발 : 1번 도시
 
    // dijstra
    while (!pq.empty())
    {
        int here = pq.top().second.first; // 현재 위치
        LL total = -pq.top().first; // 총 비용
        LL minCost = pq.top().second.second; // 지금까지 거쳐간 도시들 중에서의 가장 싼 기름값
 
        pq.pop();
 
        if (visit[here][minCost]) {
            continue;
        }
 
        visit[here][minCost] = true;
 
        // 도착
        if (here == n) {
            return total;
        }
 
        // 현재(here)에서 갈 수 있는 곳(next)
        for (auto next : v[here]) {
            LL minMoney = min(city[next.first], minCost); // 다음 도시에서 사용할 최소의 기름값 계산(현재 도시에서는 계산 X)
            LL t = total + next.second * minCost; // 현재까지 누적된 total + 거리*가장 싼 기름값
 
            pq.push({ -t,{ next.first, minMoney } });
        }
    }
 
    return -1;
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%lld %lld", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &city[i]);
    }
 
    int s, e;
    LL d;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %lld", &s, &e, &d);
        v[s].push_back({ e, d });
        v[e].push_back({ s, d });
    }
 
    printf("%lld\n", dijstra(1));
 
    return 0;
}