백준 13905번: 세부 (C++)

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

13905번: 세부

---

Solved By: MST, DFS

 

최대 스패닝 트리를 만들어서 해당하는 edge들끼리 인접 리스트를 구성하고, 인접 리스트로 DFS를 돌리면서 s에서 e로 가는 길 중 최솟값을 구하면 됩니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100001
#define ll long long
#define INF 1e9
using namespace std;

vector<pair<int, ll>> adj[MAX];
vector<pair<pair<int, int>, ll>> edges;
int parent[MAX];

int n, m, s, e;

bool cmp(pair<pair<int, int>, ll> a, pair<pair<int, int>, ll> b){
    return a.second > b.second;
}

int getRoot(int node){
    if(node == parent[node]) return node;
    else return parent[node] = getRoot(parent[node]);
}

bool find(int a, int b){
    int ga = getRoot(a);
    int gb = getRoot(b);
    
    if(ga != gb) return true;
    else return false;
}

void unionNodes(int a, int b){
    int ga = getRoot(a);
    int gb = getRoot(b);
    
    if(ga < gb) parent[gb] = ga;
    else parent[ga] = gb;
}

bool visited[MAX];
ll res;

void dfs(int from, int to, ll getValue){
    for(int i = 0; i < adj[from].size(); i++){
        int next = adj[from][i].first;
        ll distValue = adj[from][i].second;
        if(!visited[next]){
            visited[next] = true;
            if(next == to){
                res = min(distValue, getValue);
                return;
            }
            dfs(next, to, min(getValue, distValue));
            visited[next] = false;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    cin >> s >> e;
    for(int i = 0; i < m; i++){
        int v, u; ll w;
        cin >> v >> u >> w;
        edges.push_back({{v, u}, w});
    }
    
    for(int i = 1; i <= n; i++) parent[i] = i;
    sort(edges.begin(), edges.end(), cmp);
    
    for(int i = 0; i < edges.size(); i++){
        int first = edges[i].first.first;
        int second = edges[i].first.second;
        if(find(first, second)){
            unionNodes(first, second);
            ll weight = edges[i].second;
            adj[first].push_back({second, weight});
            adj[second].push_back({first, weight});
        }
    }
    
    visited[s] = true;
    dfs(s, e, INF);
    cout << res;
}