Submission #897774

#	Time	Username	Problem	Language	Result	Execution time	Memory
897774		dwuy	Cities (BOI16_cities)	C++14	0 / 100	244 ms	28616 KiB

cities

/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;

int n, k, m;
int a[10];
vector<pair<int, int>> G[MX];
vector<int> dp[MASK(5)];
int ans[MASK(5)];
int d[6][MX];
int p[6][MX];

void nhap(){
    cin >> n >> k >> m;
    for(int i=0; i<k; i++) cin >> a[i];
    for(int i=1; i<=m; i++){
        int u, v, c;
        cin >> u >> v >> c;
        G[u].push_back({v, c});
        G[v].push_back({u, c});
    }
}

void solve(){
    for(int t=0; t<k; t++){
        memset(d[t], 0x3f, sizeof d[t]);
        d[t][a[t]] = 0;
        priority_queue<pii, vector<pii>, greater<pii>> Q;
        Q.push({0, a[t]});
        while(Q.size()){
            int du, u; tie(du, u) = Q.top();
            Q.pop();
            if(du != d[t][u]) continue;
            for(pii &tmp: G[u]){
                int v, c;
                tie(v, c) = tmp;
                if(du + c < d[t][v]){
                    p[t][v] = u;
                    d[t][v] = du + c;
                    Q.push({du+c, v});
                }
            }
        }
    }
    memset(ans, 0x3f, sizeof ans);
    for(int mask=1; mask<MASK(k); mask<<=1){
        int u = __lg(mask);
        dp[mask].push_back(a[u]);
        ans[mask] = 0;
    }
    for(int mask=1; mask<MASK(k)-1; mask++){
        for(int t=0; t<k; t++) if(!(mask&MASK(t))){
            int cost = OO;
            int Mask = mask^MASK(t);
            for(int u: dp[mask]) cost = min(cost, d[t][u]);
            if(ans[mask] + cost >= ans[Mask]) continue;
            ans[Mask] = ans[mask] + cost;
            dp[Mask] = dp[mask];
            for(int u: dp[mask]) if(d[t][u] == cost){
                while((u = p[t][u])!=0) dp[Mask].push_back(u);
                break;
            }
        }
    }
    cout << ans[MASK(k) - 1];
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26