Submission #480354

#	Time	Username	Problem	Language	Result	Execution time	Memory
480354		hidden1	Cities (BOI16_cities)	C++14	0 / 100	6029 ms	49900 KiB

cities

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e15 + 7;
 
const ll MAX_N = 2e5 + 10, MAX_K = 5;
ll spec[MAX_K];
ll dist[MAX_K][MAX_N];
ll ans[MAX_N][1 << (MAX_K - 2)];
ll n, k, m;
vector<pair<ll, ll> > g[MAX_N];

void calculate(ll ind) {
    for(ll i = 0; i < MAX_N; i ++) {
        dist[ind][i] = mod;
    }
    dist[ind][spec[ind]] = 0;
    priority_queue<pair<ll, ll> > pq;
    pq.push({0, spec[ind]});

    while(!pq.empty()) {
        auto curr = pq.top(); pq.pop();
        curr.first *= -1;

        if(curr.first != dist[ind][curr.second]) {continue;}
        for(auto it : g[curr.second]) {
            if(dist[ind][it.first] > curr.first + it.second) {
                dist[ind][it.first] = curr.first + it.second;
                pq.push({dist[ind][it.first], it.first});
            }
        }
    }
}

ll getAns(ll start, ll finish) {
    for(ll i = 0; i < MAX_N; i ++) {
        for(ll j = 0; j < (1 << (MAX_K - 2)); j ++) {
            ans[i][j] = mod;
        }
    }

    ans[spec[start]][0] = 0;
    priority_queue<pair<ll, pair<ll, ll> > > pq;
    pq.push({0, {spec[start], 0}});

    while(!pq.empty()) {
        auto curr = pq.top(); pq.pop();

        curr.first *= -1;

        for(auto it : g[curr.second.first]) {
            if(ans[it.first][curr.second.second] > curr.first + it.second) {
                ans[it.first][curr.second.second] = curr.first + it.second;
                pq.push({-ans[it.first][curr.second.second], {it.first, curr.second.second}});
            }            
        }

        for(ll i = 0, skip = 0; i < k; i ++) {
            if(i == start || i == finish) {skip ++; continue;}
            if(ans[curr.second.first][curr.second.second | (1 << (i - skip))] > curr.first + dist[i][curr.second.first]) {
                ans[curr.second.first][curr.second.second | (1 << (i - skip))] = curr.first + dist[i][curr.second.first];
                pq.push({-ans[curr.second.first][curr.second.second | (1 << (i - skip))], {curr.second.first, curr.second.second | (1 << (i - skip))}});
            }            
        }
    }

    return ans[spec[finish]][(1 << (k - 2)) - 1];
}

signed main() {
    // ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k >> m;
    for(ll i = 0; i < k; i ++) {
        cin >> spec[i];
    }
    for(ll i = 0; i < m; i ++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    for(ll i = 0; i < k; i ++) {
        calculate(i);
    }
    ll ret = mod;
    for(ll i = 0; i < k; i ++) {
        for(ll j = i + 1; j < k; j ++) {
            chkmin(ret, getAns(i, j));
        }
    }
    cout << ret << endl;
    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26