인프런 커뮤니티 질문&답변

#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;

}