#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct info
{
int dst;
int cost;
};
int N, M, A, B, C, F, T;
int maxcost;
vector<info> node[100001];
bool visited[100001];
bool BFS(int cost)
{
queue<int> Q;
Q.push(F);
visited[F] = true;
while (!Q.empty())
{
int cf = Q.front();
Q.pop();
if (cf == T) return true;
for (int i = 0; i < node[cf].size(); i++)
{
int nf = node[cf][i].dst;
int nc = node[cf][i].cost;
if (visited[nf] == true) continue;
if (cost <= nc)
{
visited[nf] = true;
Q.push(nf);
}
}
}
return false;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for (int i = 0; i < M; i++)
{
cin >> A >> B >> C;
node[A].push_back({ B, C });
node[B].push_back({ A, C });
maxcost = max(maxcost, C);
}
cin >> F >> T;
int start = 0;
int end = maxcost;
while (start <= end)
{
fill(visited, visited + N + 1, false); // 조심
int mid = (start + end) / 2;
if (BFS(mid) == true) start = mid + 1;
else end = mid - 1;
}
cout << end << "\n";
return 0;
}
이분 탐색과 BFS 관련 문제였다.
Baekjoon_Link 👈 Click here