인프런 커뮤니티 질문&답변
작성한 질문수
선생님 안녕하세요. 다른 풀이에 대한 질문이 있습니다.
22.07.06 02:16 작성
·
167
0
실행
답변 1
0
2022. 07. 06. 02:24
#include <bits/stdc++.h>
using namespace std;
int board[10001][10001];
int n, m, s, e;
int can(int w)
{
queue<int> Q;
vector<int> ch(10001, 0);
ch[s] = 1;
Q.push(s);
while(!Q.empty())
{
int v = Q.front();
Q.pop();
for(int i = 1; i < 10001; i++)
{
if(board[v][i] >= w && ch[i] == 0)
{
//cout << v << " " << i << endl;
ch[i] = 1;
Q.push(i);
}
}
}
return ch[e];
}
int main()
{
ios_base::sync_with_stdio(false);
freopen("input.txt", "rt", stdin);
int lt = 1, rt = 1000000000, mid, res;
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
board[a][b] = c;
board[b][a] = c;
}
cin >> s >> e;
while(lt <= rt)
{
mid = (lt + rt) / 2;
if(can(mid))
{
//cout << "mid : " << mid << endl;
res = mid;
lt = mid + 1;
}
else
{ //cout << "else mid : " << mid << endl;
rt = mid - 1;
}
}
cout << res;
return 0;
}