백준 25430 - 다이제스타 (C++)

문제

• 문제 링크

  
   BOJ 25430 - 다이제스타 
  

• 문제 요약

$N$개의 정점으로 이루어진 그래프의 간선과 시작점, 도착점 정보가 주어진다.
항상 전에 이동했던 연결통로보다 더 길이가 긴 연결통로를 이용해야만 할 때, 운반을 완료하는 최소 이동 거리를 구해보자.

• 제한

TL : $1$ sec, ML : $512$ MB




$1 ≤ N ≤ 50,000$

$1 ≤ M ≤ 100,000$

$1 ≤ E_i ≤ 10,000,000$

알고리즘 분류

• 그래프 이론(graphs)
• 다익스트라(dijkstra)
• 자료 구조(data structures)
• 트리를 사용한 집합과 맵(tree _ set / map)

풀이

다익스트라 냄새가 물씬 나는 문제지만, 그동안 알고 있던 다익 문제들과 살짝 궤를 달리하는 신선한 문제다.

핵심은 문제에서도 주어졌듯이,
"항상 전에 이동한 연결통로보다 더 길이가 긴 연결통로를 이용해야만 한다." 가 되겠다.

이에 따라 가중치에 주목하자. 작은 가중치부터 차례로 이용해 최단 거리 테이블을 개척해 나가는 것이 바로 문제가 요구하는 바 아니겠는가 ?

---

위를 편하게 구현하기 위하여 $map$ 자료 구조를 이용해 가중치에 따른 간선 벡터를 저장하는 방식을 택했다.

또한, 기존 거리 테이블( $D[]$ ) 외에 $temp$ 거리 테이블 ( $T[]$ ) 을 추가로 정의하자.
이는 특정 가중치에 대해 기존 거리 테이블이 갱신될 수 있는지의 여부를 전수 조사하기 위함이다.

즉, 임의의 간선이 정점 $u, v$를 가중치 $c$로 이을 때 $T[u] = min(T[u], D[v] + c)$ 가 된다.
$T[v]$ 역시 같은 흐름이다.

그렇게 특정 가중치의 간선 벡터를 순회하며 $T[x]$의 값을 모두 계산했다면,
이제 기존 거리 테이블과의 비교만이 남았다.

이 과정에선 당연히 $D[x] = min(D[x], T[x])$.
이후, 사용한 $T[x]$ 를 다시 $inf$ 로 돌려주자.

최종적으로 목적지 거리 테이블의 갱신이 이뤄졌는지의 여부를 보고 답을 결정해주면 된다.

전체 코드

#include<bits/stdc++.h>
#define M 1e18
using namespace std;
 
map <int, vector<pair<int, int>>> E;
vector<long long> D(50001, M), T(50001, M);
int n, m, s, e;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int u, v, c; m--; E[c].emplace_back(u, v)) cin >> u >> v >> c;
    cin >> s >> e; D[s] = 0;
    for (auto& [c, V] : E)
    {
        for (auto& [u, v] : V)
            T[u] = min(T[u], D[v] + c), T[v] = min(T[v], D[u] + c);
        for (auto& [u, v] : V)
        {
            D[u] = min(D[u], T[u]), T[u] = M;
            D[v] = min(D[v], T[v]), T[v] = M;
        }
    }
    D[e] == M ? cout << "DIGESTA" : cout << D[e];
}

comment

끝