oj.uz

Submission #328379

# Submission time Handle Problem Language Result Execution time Memory
328379 2020-11-16T11:18:58 Z doowey Cities (BOI16_cities) C++14
100 / 100
 3867 ms 52180 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 52120 KB Output is correct
2 Correct 787 ms 51716 KB Output is correct
3 Correct 469 ms 42012 KB Output is correct
4 Correct 76 ms 15652 KB Output is correct
5 Correct 398 ms 49684 KB Output is correct
6 Correct 69 ms 15520 KB Output is correct
7 Correct 5 ms 3180 KB Output is correct
8 Correct 4 ms 3180 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3180 KB Output is correct
2 Correct 7 ms 3180 KB Output is correct
3 Correct 5 ms 3052 KB Output is correct
4 Correct 6 ms 3052 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1666 ms 51836 KB Output is correct
2 Correct 1705 ms 51300 KB Output is correct
3 Correct 1130 ms 42140 KB Output is correct
4 Correct 929 ms 35052 KB Output is correct
5 Correct 203 ms 19264 KB Output is correct
6 Correct 81 ms 17644 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3824 ms 52180 KB Output is correct
2 Correct 3845 ms 51964 KB Output is correct
3 Correct 3867 ms 51292 KB Output is correct
4 Correct 2773 ms 41944 KB Output is correct
5 Correct 1989 ms 35016 KB Output is correct
6 Correct 333 ms 19332 KB Output is correct
7 Correct 104 ms 17900 KB Output is correct