문제보고 겁만 안먹으면 금방 할 수있을텐데 말이지...

14889_스타트와 링크

#include <iostream>
#include <vector>
using namespace std;
int n,map[21][21];
bool check[21];
int res=2000001;
int startScore(vector<int> start){
    int cnt=0;
    for(int i=0; i<start.size(); i++) {
        for(int j=i+1; j<start.size(); j++) {
            cnt+=map[start[i]][start[j]]+map[start[j]][start[i]];
        }
    }
    return cnt;
}
int linkScore(){
    int cnt=0;
    vector<int> link;
    for(int i=1; i<=n; i++) {
        if(!check[i])
            link.push_back(i);
    }
    for(int i=0; i<link.size(); i++) {
        for(int j=i+1; j<link.size(); j++) {
            cnt+=map[link[i]][link[j]]+map[link[j]][link[i]];
        }
    }
    return cnt;
}
void dfs(int x, vector<int> start){
    if(start.size()==n/2) {
        int sta=startScore(start);
        int lin=linkScore();
        res=min(res,abs(sta-lin));
    } else {
        for(int i=x+1; i<=n; i++) {
            check[i]=true;
            start.push_back(i);
            dfs(i,start);
            start.pop_back();
            check[i]=false;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++)
            cin>>map[i][j];
    }
    vector<int> temp;
    dfs(0,temp);
    cout<<res<<endl;
}