oj.uz

Submission #969115

# Submission time Handle Problem Language Result Execution time Memory
969115 2024-04-24T14:11:35 Z vjudge1 Cities (BOI16_cities) C++17
0 / 100
 1101 ms 17168 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
const int K = 6;
const long long INF = 1e18;
int arr[K] , pre[N][K] , now[K];
vector<pair<int,int>> vec[N];
long long dis[N][K] , ans = 1e18;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
vector<int> path;
map<int,int> mp;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,k,m; cin >> n >> k >> m;
    for (int i=1;i<=k;i++) {
        cin >> arr[i];
        mp[arr[i]] = i;
        for (int j=1;j<=n;j++) dis[j][i] = INF;
    }
    while (m--) {
        int u,v,w; cin >> u >> v >> w;
        vec[u].push_back({w, v});
        vec[v].push_back({w, u});
    }
    for (int i=1;i<=k;i++) {
        q.push({dis[arr[i]][i]=0, arr[i]});
        while (!q.empty()) {
            auto [dist,u] = q.top(); q.pop();
            for (auto [w,v]:vec[u]) {
                if (dis[v][i] > dis[u][i] + w) {
                    pre[v][i] = u;
                    dis[v][i] = dis[u][i] + w;
                    q.push({dis[v][i], v});
                }
            }
        }
    }
    for (int i=1;i<=k;i++) now[i] = i;
    do {
        path = {arr[now[1]]};
        long long minn = 0;
        for (int i=1;i<=k;i++) {
            long long minnow=INF;
            int pos=0,st=mp[arr[i]];
            for (auto j:path) {
                if (minnow > dis[j][st]) {
                    minnow = dis[j][st];
                    pos = j;
                }
            }
            minn += dis[pos][st];
            while (pos!=arr[i]) {
                path.push_back(pos);
                pos = pre[pos][st];
            }
        }
        ans = min(ans, minn);
    } while (next_permutation(now+1, now+1+k));
    cout << ans;
    return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 677 ms 17100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 807 ms 17156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1101 ms 17168 KB Output isn't correct
2 Halted 0 ms 0 KB -