제출 #852751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852751		vjudge1	Kronican (COCI16_kronican)	C++17	10 / 100	148 ms	440 KiB

kronican

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5, M = 1e6 + 6, mod = 998244353;

int c[20][20];
int n, k;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> c[i][j];
        }
    }
    int res = INT_MAX;
    for (int i = 0; i < (1 << n); ++i) {
        if (__builtin_popcount(i) != k)
            continue;
        queue<int> q;
        vector<bool> vis(n);
        vector<int> dis(n, INT_MAX), best(n);
        for (int j = 0; j < n; ++j) {
            if ((1 << j) & i)
                q.push(j), vis[j] = 1, dis[j] = 0;
        }
        int ans = 0;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                int u = q.front();
                q.pop();
                for (int j = 0; j < n; ++j) {
                    if(j == u)
                        continue;
                    dis[j] = min(dis[j], dis[u] + c[j][u]);
                    if (dis[j] == dis[u] + c[j][u]) {
                        best[j] = c[j][u];
                    }
                    if (!vis[j]) {
                        q.push(j);
                        vis[j] = 1;
                    }
                }
            }
        }
        for (int j = 0; j < n; ++j) {
            ans += best[j];
        }
        res = min(res,ans);
    }
    cout << res << '\n';
}

• Subtask 1: 10 / 100