제출 #81697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81697		ngot23	Kronican (COCI16_kronican)	C++11	50 / 100	1426 ms	752 KiB

kronican

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=25;
int luu[N], n, k, d[N][N], tr[N][N], c[N][N], ans=1000000000;
vector <pair<int, int > > g[N];
bool fl[N];

void setup() {
    cin >> n >> k;
    rep(i, 1, n)
        rep(j, 1, n) {
            int u;
            cin >> u;
            if(i==j) continue;
            g[j].push_back(make_pair(i, u));
            c[i][j]=u;
        }
}

void IJK(int s, int d[], int tr[]) {
    rep(i, 1, n) d[i]=1000000000;
    d[s]=0;
    priority_queue <pair<int, int > > p;
    p.push(make_pair(0, s));
    while(!p.empty()) {
        int l=-p.top().first;
        int u=p.top().second;
        p.pop();
        if(l>d[u]) continue;
        for(auto P:g[u]) {
            int v=P.first, ts=P.second;
            if(fl[v]) continue;
            if(d[v]>d[u]+ts) {
                d[v]=d[u]+ts;
                tr[v]=u;
                p.push(make_pair(-d[v], v));
            }
        }
    }
}

void tinh() {
    memset(fl, false, sizeof fl);
    rep(i, 1, k) fl[luu[i]]=true;
    rep(i, 1, k) IJK(luu[i], d[luu[i]], tr[luu[i]]);

    int ret=0;
    rep(i, 1, n) {
        if(fl[i]) continue;
        int xx=1000000000;
        rep(j, 1, k) {
            int u=luu[j];
            xx=min(xx, c[i][tr[u][i]]);
        }
        ret+=xx;
    }
    ans=min(ans, ret);
}

void duyet(int u) {
    rep(x, luu[u-1]+1, n) {
        luu[u]=x;
        if(u==k) tinh();
        else duyet(u+1);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    setup();
    if(k>=n) return cout << 0, 0;
    duyet(1);
    cout << ans;
    return 0;
}

• Subtask 1: 50 / 100