oj.uz

답안 #480357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480357 2021-10-15T18:16:36 Z hidden1 Cities (BOI16_cities) C++14
74 / 100
 6000 ms 77132 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;

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

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 20556 KB Output is correct
2 Correct 11 ms 20556 KB Output is correct
3 Correct 15 ms 22156 KB Output is correct
4 Correct 21 ms 23824 KB Output is correct
5 Correct 24 ms 25376 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 885 ms 42056 KB Output is correct
2 Correct 876 ms 42012 KB Output is correct
3 Correct 464 ms 30264 KB Output is correct
4 Correct 105 ms 31548 KB Output is correct
5 Correct 366 ms 33836 KB Output is correct
6 Correct 104 ms 29696 KB Output is correct
7 Correct 19 ms 22432 KB Output is correct
8 Correct 14 ms 20700 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 24140 KB Output is correct
2 Correct 27 ms 24064 KB Output is correct
3 Correct 26 ms 24028 KB Output is correct
4 Correct 24 ms 24004 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3044 ms 55224 KB Output is correct
2 Correct 2601 ms 52980 KB Output is correct
3 Correct 1933 ms 40964 KB Output is correct
4 Correct 1753 ms 45488 KB Output is correct
5 Correct 445 ms 38576 KB Output is correct
6 Correct 146 ms 35228 KB Output is correct

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6035 ms 77132 KB Time limit exceeded
2 Halted 0 ms 0 KB -