백준 20168 골목 대장 호석 - 기능성

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

20168번: 골목 대장 호석 - 기능성

그래프 탐색을 통해 푸는 문제였습니다.

N개의 노드와 M개의 에지로 이루어진 그래프라고 볼 수 있습니다. 노드의 개수가 최대 10개고 시작과 도착이 정해져있으며 한 노드에서 특정 노드로 가는 에지는 최대 1개입니다. 따라서 그래프 탐색의 시간복잡도는 O(8!)가 됩니다.

그래프 탐색과정에서 최대요금만 기록해가며 도착 노드에 도달했을때 현재까지 나온 가장작은 최대요금과 비교하면 됩니다.

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
bool visit[11];
vector<vector<pair<int,int>>> E(11,vector<pair<int,int>>());
int N,M,A,B,C;
int solve=2e9;
int mymax(int a,int b){
    return a>b ? a : b;
}
void dfs(int now,int suchisim,int cost){
    visit[now]=true;
    if(suchisim>=solve || cost>C) return;
    if(now==B){
        if(cost<=C && suchisim<solve){
            solve=suchisim;
        }
        return;
    }
    for(auto i : E[now]){
        if(!visit[i.first]) dfs(i.first,mymax(suchisim,i.second),cost+i.second);
        visit[i.first]=false;
    }
}
int main(){
    cin>>N>>M>>A>>B>>C;
    for(int x=0;x<M;x++){
        int src,dst,cost;
        cin>>src>>dst>>cost;
        E[src].push_back({dst,cost});
        E[dst].push_back({src,cost});
    }
    dfs(A,0,0);
    if(solve==2e9){
        cout<<-1;
    }
    else{
        cout<<solve;
    }
}