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


bfs 에서 노드순서대로 완전탐색 하는게 문제인거 같은데

어떤식으로 접근해야 될까요... 




#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
int N;// 알고리즘 개수
int M;// 최소한 배우고자 하는 알고리즘의 개수
vector<int> v;// 각 알고리즘 배우는데 필요한 시간
vector<pair<int,int>> arr[100001];
bool visited[100001];
bool bfs(int MID){// 이 공부량으로 M이상 거쳐갈 수 있는지

    // 공부량은 누적된다.
    // 일정 공부량 이하가되면 노드에 진입할 수 있게 짜기
    for(int i=0;i<N;i++){
        vector<int>temp;
        int maxi=0;
        int counT=1;
        for(int t=0;t<v.size();t++){
            temp.push_back(v[t]);
        }
        // mid 랑 비교
        if(temp[i]>MID){
            continue;
        }
        queue<int> q;
        // 현재 노드/현재 공부량
        q.push(i+1);
        // 여기서는 1번노드, 18값,카운트 1
        fill_n(visited,100001,false);
        visited[i+1]=true;
        while(!q.empty()){
           
            int now=q.front();
           
           
           
           
            q.pop();
            if(counT==M){
               
                return true;
            }
            for(int t=0;t<arr[now].size();t++){
                int next=arr[now][t].first;
                int m_cost=arr[now][t].second;
                temp[next-1]-=m_cost;
               
                if(MID<temp[next-1]){
                    continue;
                }
                if(visited[next]==true){
                    continue;
                }
                visited[next]=true;
                q.push(next);counT+=1;

            }
        }

    }  
    return false;    
}
int main(){
    cin>>N>>M;
    int a;
    for(int i=0;i<N;i++){
        scanf("%d",&a);
        v.push_back(a);
    }
    int R;
    cin>>R;
    int s,e,c;
    for(int i=0;i<R;i++){
       
        scanf("%d %d %d",&s,&e,&c);
        arr[s].push_back({e,c});
    }
    int start=1;
    int end=100000000;
    while(start<=end){
       
        int mid=(start+end)/2;
       
        if(bfs(mid)==true){
            end=mid-1;
        }else{
            start=mid+1;
        }
    }
    cout<<start;
}