提出 #64123310

---

ソースコード 拡げる

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

#define rep(i, n) for (int i = 0; i < (n); i++)
// #define DEBUG

int N, M;
int A[11][11];
bool give[11][11];

int ans = INT_MAX;
int sum = 0;
bool hasRun[11];

void dfs(
    int dep,
    int lastRunner)
{
    if (dep == N)
    {
        ans = min(ans, sum);
        return;
    }

    for (int i = 1; i <= N; i++)
    {   
        // もう走ってる
        if(hasRun[i]){
            continue;
        }

        // 噂があるので渡せない
        if (give[i][lastRunner])
        {
            continue;
        }

        hasRun[i] = true;
        sum += A[i][dep + 1];
        
        dfs(dep + 1, i);

        hasRun[i] = false;
        sum -= A[i][dep + 1];
    }
}

int main()
{
#ifdef DEBUG
    freopen("input/in.txt", "r", stdin);
#endif

    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> A[i][j];
        }
    }

    cin >> M;
    for (int i = 0; i < M; i++)
    {
        int x, y;
        cin >> x >> y;
        give[x][y] = true;
        give[y][x] = true;
    }

    dfs(0, 0);

    if (ans == INT_MAX)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans << endl;
    }

    return 0;
}

提出情報

ジャッジ結果