【題解】AtCoder ABC 183C – Travel

【題目敘述】https://atcoder.jp/contests/abc183/tasks/abc183_c
【解題想法】DFS

#include <bits/stdc++.h>
using namespace std;

int n, k, t[10][10], used[10], cnt;

void f(int x, int tot){
    bool flag = false;
    for (int i = 2; i <= n; i++){
        if (!used[i]){
            flag = true;
            used[i] = 1;
            f(i, tot+t[x][i]);
            used[i] = 0;
        }
    }
    if (!flag){
        tot += t[x][1];
        if (tot == k) cnt++;
    }
}

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cin >> t[i][j];
        }
    }
    f(1, 0);
    cout << cnt << "\n";
}

分享本文 Share with friends