yhm1620

#include <bits/stdc++.h>
using namespace std;
&nbsp;
int board[10001][10001];
int n, m, s, e;
&nbsp;
int can(int w)&nbsp;
{
&nbsp; queue<int> Q;
&nbsp; vector<int> ch(10001, 0);
&nbsp;
&nbsp; ch[s] = 1;
&nbsp; 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 << " " <
 ch[i] = 1;
 Q.push(i);
 }
 }
 }
 
 return ch[e];
}
 
&nbsp;
int main()
{
 ios_base::sync_with_stdio(false);&nbsp;
 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;&nbsp;
 }
 }
 cout << res;
 
 return 0;
}
&nbsp;

yhm1620

投稿