백준 25430번 다이제스타 - C++ 풀이

---

 

1. 다익스트라를 사용하여 최단거리를 구한다.
2. 다익스트라 과정에서 마지막으로 이용한 간선의 가중치 w를 저장해 두고 더 큰 가중치의 간선만 사용하도록 한다.
3. 같은 노드에 도착하더라도 w에 따라 이용할 수 있는 다음 간선이 달라지므로 dist 배열은 dist[node][w]의 형태로 운영한다.

 

1. 다익스트라를 사용하여 최단거리를 구한다.

 다익스트라 알고리즘을 사용하여 두 노드 사이의 최단거리를 구할 수 있다.

 

2. 다익스트라 과정에서 마지막으로 이용한 간선의 가중치 w를 저장해두고 더 큰 가중치의 간선만 사용하도록 한다.

 단, 문제에서 주어진 조건에 따라 경로 내 간선의 가중치는 오름차순이 되어야 한다. 따라서 다익스트라 과정에서 이 조건을 만족할 수 있도록 마지막으로 이용한 간선의 가중치 w를 우선순위 큐 노드에 함께 저장해 두고, 다음 간선은 w 초과인 간선만 사용하도록 한다.

 

3. 같은 노드에 도착하더라도 w에 따라 이용할 수 있는 다음 간선이 달라지므로 dist 배열은 dist[node][w]의 형태로 운영한다.

 같은 idx번 노드에 도착하더라도 마지막으로 이용한 간선의 가중치 w에 따라 다음에 이용할 수 있는 간선이 달라질 수 있기 때문에 dist 배열을 일반적인 다익스트라처럼 운영해서는 안된다.

 아래와 같은 상황이 그 예이다. 시작 노드에서 4번 노드로 가는 최단 경로는 시작-1-4를 거쳐 총 7의 거리로 이동하는 방법이다. 하지만 이렇게 이동하면 4번 노드에서 도착 노드로 갈 수 없다. 시작-2-3-4로 이동해야 도착 노드로 갈 수 있다.

  따라서 "dist[N][w]: 가중치가 w인 간선을 타고 N번 노드에 도착하는 최단 거리"의 형태로 dist를 관리해준다. 이때 w의 범위가 10^7이므로 map을 사용하여 해당 노드에 연결된 간선의 가중치만 관리해주면 된다.

반응형

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> Node;   // {d, {w, curr}}
const ll INF = 1e12+1;

int N, M, S, E;
vector<pll> adjs[50001];
map<int, ll> dist[50001];   // dist[N][w] = d

ll dijkstra() {
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    ll ret = INF;
    
    dist[S][0] = 0;
    pq.push({0, {0, S}});
    
    while (!pq.empty()) {
        ll d = pq.top().first;
        ll w = pq.top().second.first;
        ll curr = pq.top().second.second;
        pq.pop();
        
        if (curr == E) ret = min(ret, d);
        if (d > dist[curr][w]) continue;
        
        for (auto adj: adjs[curr]) {
            ll next = adj.first;
            ll nw = adj.second;
            
            if (nw <= w) continue;
            if (d+nw > dist[next][nw]) continue;
            
            dist[next][nw] = d+nw;
            pq.push({d+nw, {nw, next}});
        }
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for (int i=0; i<M; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        
        adjs[s].push_back({e, w});
        adjs[e].push_back({s, w});
        
        dist[s][w] = INF;
        dist[e][w] = INF;
    }
    cin >> S >> E;
    
    ll ans = dijkstra();
    
    if (ans == INF) cout << "DIGESTA";
    else cout << ans;
    
    return 0;
}