freight

freight.cpp

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

int N, M;
bool visit[10001] = {0, };
int strt, dest, sol = 0;
vector< pair<int, int> > brdVec[10001]; // 섬에서 연결된 <다른 섬, 제한 무게> 벡터

bool dfs(int cur, int lmt){
  if(visit[cur]) return false;
  if(cur == dest) return true;

  visit[cur] = true;
  for (auto b : brdVec[cur])
	{
		int nxt = b.first;  // 섬에서 연결된 다음 섬의 번호
		int wgt = b.second; // 해당 섬과 연결된 다리의 제한 무게
    if(wgt >= lmt){ if(dfs(nxt, lmt)) return true; }
  }
  return false;
}

int main(){
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int A, B, C;
    cin >> A >> B >> C;
    brdVec[A].push_back(make_pair(B, C));
		brdVec[B].push_back(make_pair(A, C));
  }
  cin >> strt >> dest;

  int frt = 1;
  int end = 1e9;

  while(frt <= end){
    int mid = (frt + end) / 2; // frt / end를 옮겨가며 해답을 찾을 때까지 이진탐색
    memset(visit, false, sizeof(visit));
    if(dfs(strt, mid)){ // dfs가 목적지에 도달가능하면 sol을 업데이트 후, frt를 올린다
      sol = mid;
      frt = mid + 1;
    } else {
      end = mid - 1; // dfs가 목적지에 도달불가하면 end를 내린다
    }
  }

  cout << sol << endl;

  return 0;
}