Submission #969115

#	Time	Username	Problem	Language	Result	Execution time	Memory
969115		vjudge1	Cities (BOI16_cities)	C++17	0 / 100	1101 ms	17168 KiB

cities

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26