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

문제 설명

문제 링크

http://icpc.me/20168

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

풀이

백트레킹을 이용하여 풀 수 있다.

n의 크기가 매우 작으니 백트레킹을 하며 모든 경우를 확인해보면 된다.

코드

#include <cstdio>
#include <algorithm>

using namespace std;

int d[11][11];
int n, m, a, b, c, ans = 1e9, totalSum = 1e9; 
bool visited[11];

void solve(int cur, int total, int maxCost) {
    if (total > c) return;
    if (cur == b) {
        ans = min(ans , maxCost);
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!d[cur][i] || visited[i]) continue;
        visited[i] = true;
        solve(i, total + d[cur][i], max(maxCost, d[cur][i]));
        visited[i] = false;
    }
}

int main() {
    scanf("%d %d %d %d %d", &n, &m, &a, &b, &c);
    while (m--) {
        int x, y, z; scanf("%d %d %d", &x, &y, &z);
        d[x][y] = d[y][x] = z;
    }
    solve(a, 0, 0);
    printf("%d", ans == 1e9 ? -1 : ans);
}