백준 13905 세부

문제 URL : https://www.acmicpc.net/problem/13905

13905번: 세부

 

문제접근법 :  요약하자면 크루스칼 + bfs문제입니다. 

난이도는 높은편은 아니지만 해맸습니다. 질문에서 갈수없는 경우가 있다는것을 보고 문제에 적혀있질않아서

해맸습니다.

 

크루스칼 같은경우는 비용이 가장 큰것기준으로 정렬을해서 간선을 만들어나갑니다.

 

그간선대로 bfs를 적용해서 출발지점에서 끝지점까지 최소비용을 저장해서 답을 내주면 됩니다.

 

소스코드 :

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> v[100001];
int n,m;
int s,e;
vector<int>parent;
vector<tuple<int,int,int>> adj;
void input()
{
    cin>>n>>m;
    cin>>s>>e;
    int a,b,c;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        adj.push_back({-c,a,b});
    }
}
int find(int idx){
    if(parent[idx]==idx)return idx;
    return parent[idx]=find(parent[idx]);
}
bool merge(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b)return false;
    if(a<b)parent[b]=a;
    else parent[a]=b;
    return true;
}
void solve()
{
    parent.resize(n+1);
    for(int i=1;i<=n;i++)parent[i]=i;
    sort(adj.begin(),adj.end());
    for(auto[c,a,b]:adj){
        if(merge(a,b)){
            v[a].push_back({b,-c});
            v[b].push_back({a,-c});
        }
    }
    
    vector<int> check(n+1),cost(n+1,1e8);
    queue<int> q;
    q.push(s);
    check[s]=1;
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        for(int i=0;i<v[cur].size();i++){
            int next = v[cur][i].first;
            int ncost = v[cur][i].second;
            if(check[next]==0){
                cost[next]=min(cost[cur],ncost);
                check[next]=1;
                q.push(next);
            }
        }
    }
    cout<<(cost[e]==1e8?0:cost[e])<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("input.txt", "r", stdin);
    input();
    solve();
}

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.