【洛谷-P1396】解题报告（二分，BFS）

//bfs+二分
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n - 1; i >= a; --i)
#define fi first
#define se second
#define pb push_back
#define np next_permutation
#define INF 0x3f3f3f3f
#define EPS 1e-8
#define eps '\n'

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef vector<int> vi;

const int maxn = 1e5 + 5;

struct edge {
    int u, v, w;
    edge(int _u, int _v, int _w)
: u(_u)
        , v(_v)
        , w(_w)
    {
    }
    edge() {}
};
vector<edge> e[maxn];
int vis[maxn];
int n, m, ans, ss, tt;

inline void addEdge(int u, int v, int w)
{
    e[u].push_back(edge(u, v, w));
}

bool check(int mid)
{
    queue<int> q;
    memset(vis, 0, sizeof(int) * (n + 1));
    q.push(ss);
    vis[ss] = 1;
    int now, nxt;
    while (!q.empty()) {
        now = q.front();
        q.pop();
        rep(i, 0, e[now].size())
        {
            int tempv = e[now][i].v;
            int tempw = e[now][i].w;
            if (vis[tempv] || tempw > mid)
                continue;
            else {
                vis[tempv] = 1;
                if (tempv == tt)
                    return true;
                q.push(tempv);
            }
        }
    }

    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    while (cin >> n >> m >> ss >> tt) {
        ans = 1e4 + 5;
        int tu, tv, tw;
        rep(i, 0, n + 1) e[i].clear();
        rep(i, 1, m + 1)
        {
            cin >> tu >> tv >> tw;
            addEdge(tu, tv, tw);
            addEdge(tv, tu, tw);
        }
        int l = 0;
        int r = 1e4 + 5;
        int mid;
        while (l < r) {
            mid = (l + r) >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        cout << l << endl;
    }
}