[13905] 세부 (다른방법으로 풀어보기)

### Parametric Search + BSF ###

[13905] 세부 : http://boj.kr/13905

- 다익스트라 or MST+LCA 로도 풀 수 있다고 한다. 나중에 도전해봐야겠다..!!

<소스코드>

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
struct P { int to, w; };
 
int n, m;
int s, e;
vector<P> g[100001];
 
bool isPossible(int mid)
{
    queue<int> q;
    q.push(s);
 
    vector<bool> visited(n+1, 0);
    visited[s] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
 
        for(auto &p : g[cur]) {
            int next = p.to;
            int w = p.w;
            if(!visited[next] && mid <= w) {
                if(next == e) return 1;
                visited[next] = 1;
                q.push(next);
            }
        }
    }
    return 0;
}
 
int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &e);
 
    while(m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back((P){b, c});
        g[b].push_back((P){a, c});
    }
 
    if(s == e) return !printf("0\n");
 
    int S=1, E=1000000;
    while(S <= E) {
        int mid = (S+E)/2;
        if(isPossible(mid)) S = mid+1;
        else E = mid-1;
    }
    printf("%d\n", S-1);
    return 0;
}
 

>> [1939] 중량제한 문제와 동일한 문제.

>> 근데 조건 한개가 다르다. 중량제한 문제는 출발지와 도착지가 서로 다르다고 명시가 되어 있는데, 위 문제는 그렇지 않다. 

>> 그래서 47 라인이 추가되었다.