oj.uz

답안 #478490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
478490 2021-10-07T17:50:36 Z Lobo Cities (BOI16_cities) C++17
14 / 100
 3706 ms 115332 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] = 0;
            for(ii id = 0; id < k; id++) {
                if((mask&(1<<id)) != 0) d[i][mask]+= dd[id][i];
            }

            pq.push(mp(-d[i][mask],mp(i,mask)));
        }
    }

    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][mask],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);
    }

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5456 KB Output is correct
2 Correct 3 ms 5456 KB Output is correct
3 Correct 3 ms 5496 KB Output is correct
4 Incorrect 3 ms 5556 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 894 ms 74168 KB Output is correct
2 Correct 889 ms 73328 KB Output is correct
3 Correct 624 ms 67164 KB Output is correct
4 Correct 94 ms 18424 KB Output is correct
5 Correct 480 ms 67256 KB Output is correct
6 Correct 84 ms 18228 KB Output is correct
7 Correct 7 ms 6276 KB Output is correct
8 Correct 6 ms 6096 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 6352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1751 ms 87452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3706 ms 115332 KB Output isn't correct
2 Halted 0 ms 0 KB -