[1939번] 중량제한

문제 출처 :

https://www.acmicpc.net/problem/1939

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분탐색

2. BFS

이 문제는 이분탐색과 BFS를 이용하면 되는 문제이다.

이때 이분탐색은 중량을 이분탐색으로 결정하고

BFS는 그 중량을 BFS로 돌려 도착점까지 갈 수 있는지 확인해본다면 결과값을 구할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

#include <iostream> #include <cstdio> #include <queue> #include <algorithm> #include <vector> #include <memory.h>   using namespace std;   typedef pair<int, int> pii;   vector<pii> vc[10002]; bool visit[10002];   int main() {     int n, m;     scanf("%d %d", &n, &m);       int start = 0, end = 0;     for (int i = 0; i < m; i++)     {         int from, to, val;         scanf("%d %d %d", &from, &to, &val);           vc[from].push_back({ to, val });         vc[to].push_back({ from, val });           end = max(end, val);     }       int s, e;     scanf("%d %d", &s, &e);       int ans = 0;     while (start <= end)     {         memset(visit, 0, sizeof(visit));           bool chk = false;         int mid = (start + end) / 2;         queue<int> q;           q.push(s);           while (!q.empty())         {             int here = q.front();             q.pop();               visit[here] = true;               if (here == e)             {                 chk = true;                 ans = max(ans, mid);                 break;             }               for (int i = 0; i < vc[here].size(); i++)             {                 int next = vc[here][i].first;                 int nextVal = vc[here][i].second;                   if (!visit[next] && nextVal >= mid)                     q.push(next);             }         }           if (chk)             start = mid + 1;         else             end = mid - 1;     }       printf("%d", ans);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus