세부

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

 

위의 그림을 순서대로 구현하면 된다.

 

 

섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)

시간 제한이 1초이므로

완전 탐색하면 무조건 시간 초과 난다.

 

숭이에서 혜빈이까지 단방향으로 가면 되는거니까

즉, 사이클이 없다.

가중치가 최대로 되게 해야하는

최소 신장 트리 문제이다. (뭔가 말이 이상하다)

 

최소 신장 트리는 "유니온 파인드"로 구현한다.

 

1. 가중치가 최대로 되게

모든 정점을 연결하는 최대 신장 트리를 만든다.

 

2. 최대 신장 트리를 따라서

숭이에서 혜빈이까지 BFS로 경로를 만든다.

BFS를 돌리면서 visited 배열에

가중치의 최솟값을 저장한다.

그러기 위해서 처음의 visited 배열은 INF로 초기화되어야한다.

 

+ queue STL를 써도 되지만

큐를 직접 구현해보자.

 

이렇게 한다.

단점은 QUEUE_SIZE를 알아야한다는 것이지만

조건이 크다면 이게 훨씬 빠르다.

 

<소스 코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
 
using namespace std;
 
#define INF 99999999
 
int n, m;
int startnode, endnode;
 
struct Edge {
    int u, v, w;
};
 
vector<Edge> graph;
 
vector<pair<int, int>> tree[100004];
 
// sorting 용 내림차순
bool operator < (Edge& a, Edge& b) {
    return a.w > b.w;
}
 
int parent[100004];
 
int find(int a) {
    if (parent[a] == a)
        return a;
 
    return parent[a] = find(parent[a]);
}
 
void unionfunc(int a, int b) {
    a = find(a);
    b = find(b);
 
    if (a != b)
        parent[b] = a;
}
 
bool isSame(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return true;
    else
        return false;
}
 
void kruskal() {
    // 그래프를 가중치 내림차순 정렬
    sort(graph.begin(), graph.end());
 
    for (int i = 1; i <= n; i++)
        parent[i] = i;
 
    for (int i = 0; i < graph.size(); i++) {
        int a = graph[i].u;
        int b = graph[i].v;
        int w = graph[i].w;
 
        // 사이클을 이루지 않으면 노드를 연결
        // 즉, 조상이 같지 않다면!
        if (!isSame(a, b)) {
            unionfunc(a, b);
            // 양방향 그래프로 최대 신장 트리 만들기
            tree[a].push_back({ b, w });
            tree[b].push_back({ a, w });
        }
    }
}
 
int Queue[100010], Front, Rear;
 
// 최대 신장 트리를 따라서 목적지까지
int bfs() {
    vector<int> visited(n + 1, INF);
    Front = Rear = -1;
    Queue[++Rear] = startnode;
 
    while (Front != Rear) {
        int x = Queue[++Front];
    
        for (int i = 0; i < tree[x].size(); i++) {
            int nx = tree[x][i].first;
            int w = tree[x][i].second;
 
            if (visited[nx] != INF)
                continue;
            visited[nx] = min(w, visited[x]);
            Queue[++Rear] = nx;
        }
    }
    return visited[endnode];
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    cin >> startnode >> endnode;
 
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph.push_back({ a, b, c });
    }
 
    kruskal();
 
    int ans = bfs();
 
    // 못들고가면 최대 개수 0
    if (ans == INF)
        cout << 0 << '\n';
    else
        cout << ans << '\n';
}