oj.uz

Submission #852751

# Submission time Handle Problem Language Result Execution time Memory
852751 2023-09-22T16:17:01 Z vjudge1 Kronican (COCI16_kronican) C++17
10 / 100
 148 ms 440 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Incorrect 1 ms 344 KB Output isn't correct
5 Incorrect 3 ms 344 KB Output isn't correct
6 Incorrect 2 ms 344 KB Output isn't correct
7 Incorrect 11 ms 344 KB Output isn't correct
8 Incorrect 19 ms 344 KB Output isn't correct
9 Incorrect 5 ms 344 KB Output isn't correct
10 Correct 148 ms 440 KB Output is correct