oj.uz

Submission #478494

# Submission time Handle Problem Language Result Execution time Memory
478494 2021-10-07T18:17:55 Z Lobo Cities (BOI16_cities) C++17
14 / 100
 4806 ms 127080 KB 
#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e16 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 220000

ii n, k, m;
ll dd[6][maxn], d[maxn][50];
vector<pair<ii,ll>> g[maxn];
vector<ii> ci;

void shortp(ii id) {
    for(ii i = 1; i <= n; i++) {
        dd[id][i] = INFll;
    }

    dd[id][ci[id]] = 0;

    priority_queue<pair<ll,ii>> pq; pq.push(mp(0,ci[id]));

    while(pq.size()) {
        ii u = pq.top().sc;
        ll dist = -pq.top().fr;
        pq.pop();

        if(dist != dd[id][u]) continue;

        for(auto V : g[u]) {
            ii v = V.fr;
            ll w = V.sc;

            if(dd[id][u] + w < dd[id][v]) {
                dd[id][v] = dd[id][u] + w;
                pq.push(mp(-dd[id][v],v));
            }
        }
    }
}

void shortp1() {
    priority_queue<pair<ll,pair<ii,ii>>> pq;

    for(ii i = 1; i <= n; i++) {
        for(ii mask = 0; mask < (1<<k); mask++) {
            d[i][mask] = INFll;
        }
        d[i][0] = 0;
        pq.push(mp(0,mp(i,0)));
    }

    while(pq.size()) {
        ii u = pq.top().sc.fr;
        ii mask = pq.top().sc.sc;
        ll dist = -pq.top().fr;
        pq.pop();

        if(dist != d[u][mask]) continue;
    
        for(auto V : g[u]) {
            ii v = V.fr;
            ll w = V.sc;

            for(ii id = 0; id < k; id++) {
                if((mask&(1<<id)) != 0) continue;
                ii mask1 = mask|(1<<id);

                if(d[v][mask1] > d[u][mask] + w + dd[id][v]) {
                    d[v][mask1] = d[u][mask] + w + dd[id][v];
                    pq.push(mp(-d[v][mask1],mp(v,mask1)));
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    cin >> n >> k >> m;

    for(ii i = 0; i < k; i++) {
        ii x; cin >> x;
        ci.pb(x);
    }

    for(ii i = 0; i < m; i++) {
        ii u, v;
        ll w;
        cin >> u >> v >> w;

        g[u].pb(mp(v,w));
        g[v].pb(mp(u,w));
    }

    for(ii i = 0; i < k; i++) {
        shortp(i);
    }

    for(ii i = 1; i <= n; i++) g[i].pb(mp(i,0));

    shortp1();

    ll ans = INFll;

    for(ii i = 1; i <= n; i++) {
        ans = min(ans, d[i][(1<<k)-1]);
    }

    cout << ans << endl;

}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5452 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5464 KB Output is correct
4 Correct 3 ms 5452 KB Output is correct
5 Incorrect 4 ms 5456 KB Output isn't correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1151 ms 76300 KB Output is correct
2 Correct 1053 ms 75236 KB Output is correct
3 Correct 718 ms 72560 KB Output is correct
4 Correct 99 ms 16048 KB Output is correct
5 Correct 595 ms 67268 KB Output is correct
6 Correct 80 ms 15288 KB Output is correct
7 Correct 10 ms 6348 KB Output is correct
8 Correct 7 ms 6220 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6352 KB Output is correct
2 Incorrect 10 ms 6404 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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