oj.uz

답안 #478495

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
478495 2021-10-07T18:30:45 Z Lobo Cities (BOI16_cities) C++17
100 / 100
 5014 ms 129112 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(ii id = 0; id < k; id++) {
            if((mask&(1<<id)) != 0) continue;
            ii mask1 = mask|(1<<id);

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

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

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

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
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5452 KB Output is correct
2 Correct 3 ms 5452 KB Output is correct
3 Correct 3 ms 5452 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 3 ms 5452 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 987 ms 65660 KB Output is correct
2 Correct 926 ms 64692 KB Output is correct
3 Correct 603 ms 60584 KB Output is correct
4 Correct 75 ms 15044 KB Output is correct
5 Correct 471 ms 60792 KB Output is correct
6 Correct 66 ms 14772 KB Output is correct
7 Correct 7 ms 6220 KB Output is correct
8 Correct 5 ms 6092 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 6348 KB Output is correct
2 Correct 11 ms 6348 KB Output is correct
3 Correct 9 ms 6352 KB Output is correct
4 Correct 8 ms 6096 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2201 ms 91112 KB Output is correct
2 Correct 1893 ms 94380 KB Output is correct
3 Correct 1553 ms 71712 KB Output is correct
4 Correct 1163 ms 58076 KB Output is correct
5 Correct 245 ms 26556 KB Output is correct
6 Correct 78 ms 20628 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5014 ms 124572 KB Output is correct
2 Correct 5000 ms 129112 KB Output is correct
3 Correct 4432 ms 128016 KB Output is correct
4 Correct 3522 ms 121892 KB Output is correct
5 Correct 2562 ms 74640 KB Output is correct
6 Correct 463 ms 31100 KB Output is correct
7 Correct 118 ms 20932 KB Output is correct