Submission #328379

#	Time	Username	Problem	Language	Result	Execution time	Memory
328379		doowey	Cities (BOI16_cities)	C++14	100 / 100	3867 ms	52180 KiB

cities

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>


using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 100;
const int K = 5;
const ll inf = (ll)1e18;
vector<pii> T[N];
ll dist[N][1 << K];

struct state{
    ll dis;
    int node;
    int mask;
    bool operator<(const state &q) const {
        return dis > q.dis;
    }
};

bool use[N][1 << K];

int main(){
    fastIO;
    int n, k, m;
    cin >> n >> k >> m;
    vector<int> q(k);
    for(int i =0 ; i < k ; i ++ ){
        cin >> q[i];
    }
    int u, v;
    ll w;
    for(int i = 0 ; i < m ; i ++ ){
        cin >> u >> v >> w;
        T[u].push_back(mp(v, w));
        T[v].push_back(mp(u, w));
    }
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j < (1 << k); j ++ ){
            dist[i][j] = inf;
        }
    }
    for(int j = 0 ; j < k ; j ++ ){
        dist[q[j]][(1<<j)]=0;
    }
    int node;
    ll dd;
    for(int ms = 1 ; ms < (1 << k) ; ms ++ ){
        for(int c = 0 ; c <= ms ; c ++ ){
            if(ms & c){
                for(int i = 1 ; i <= n; i ++ ){
                    dist[i][ms] = min(dist[i][ms], dist[i][c]+dist[i][(ms^c)]);
                }
            }
        }
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        for(int i = 1; i <= n; i ++ ){
            if(dist[i][ms] == inf) continue;
            pq.push(mp(dist[i][ms], i));
        }
        while(!pq.empty()){
            node = pq.top().se;
            dd = pq.top().fi;
            pq.pop();
            if(use[node][ms]) continue;
            use[node][ms]=true;
            for(auto x : T[node]){
                if(dist[x.fi][ms] > dist[node][ms] + x.se){
                    dist[x.fi][ms] = dist[node][ms] + x.se;
                    pq.push(mp(dist[x.fi][ms],x.fi));
                }
            }

        }

    }
    ll outp = inf;
    for(int i = 1; i <= n; i ++ )
        outp = min(outp, dist[i][(1<<k)-1]);
    cout << outp << "\n";
    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:56:8: warning: variable 'dd' set but not used [-Wunused-but-set-variable]
   56 |     ll dd;
      |        ^~

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