oj.uz

Submission #480359

# Submission time Handle Problem Language Result Execution time Memory
480359 2021-10-15T18:18:55 Z hidden1 Cities (BOI16_cities) C++14
100 / 100
 5443 ms 81132 KB 
#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;

        if(curr.first != ans[curr.second.first][curr.second.second]) {continue;}

        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 ++) {
        chkmin(ret, getAns(i, (i + 1) % k));
    }
    cout << ret << endl;
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20580 KB Output is correct
2 Correct 14 ms 20556 KB Output is correct
3 Correct 17 ms 22220 KB Output is correct
4 Correct 17 ms 23756 KB Output is correct
5 Correct 20 ms 25300 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 42380 KB Output is correct
2 Correct 762 ms 41960 KB Output is correct
3 Correct 418 ms 30304 KB Output is correct
4 Correct 89 ms 31544 KB Output is correct
5 Correct 397 ms 33812 KB Output is correct
6 Correct 76 ms 29748 KB Output is correct
7 Correct 17 ms 22348 KB Output is correct
8 Correct 14 ms 20764 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24108 KB Output is correct
2 Correct 24 ms 24056 KB Output is correct
3 Correct 22 ms 24012 KB Output is correct
4 Correct 23 ms 24016 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2132 ms 55000 KB Output is correct
2 Correct 1842 ms 53008 KB Output is correct
3 Correct 1401 ms 40896 KB Output is correct
4 Correct 1094 ms 45344 KB Output is correct
5 Correct 264 ms 38172 KB Output is correct
6 Correct 99 ms 35184 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5443 ms 77000 KB Output is correct
2 Correct 5405 ms 81132 KB Output is correct
3 Correct 4750 ms 80092 KB Output is correct
4 Correct 3703 ms 69724 KB Output is correct
5 Correct 2807 ms 61548 KB Output is correct
6 Correct 508 ms 44428 KB Output is correct
7 Correct 135 ms 41292 KB Output is correct