oj.uz

Submission #647479

# Submission time Handle Problem Language Result Execution time Memory
647479 2022-10-02T17:24:16 Z PoonYaPat Cities (BOI16_cities) C++14
100 / 100
 2003 ms 75136 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

int a[6],n,m,k;
ll dp[33][200001];
vector<pii> adj[200001];

void dij(ll *dis) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    bool vis[200001];
    memset(vis,0,sizeof(vis));
    for (int i=1; i<=n; ++i) q.push(pii(dis[i],i));
    while (!q.empty()) {
        ll node=q.top().second;
        q.pop();

        if (vis[node]) continue;
        vis[node]=true;

        for (auto s : adj[node]) {
            ll des=s.first, w=s.second;
            if (dis[des]>dis[node]+w) {
                dis[des]=dis[node]+w;
                q.push(pii(dis[des],des));
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (int i=0; i<32; ++i) for (int j=1; j<=200000; ++j) dp[i][j]=1e18;
    cin>>n>>k>>m;
    for (int i=0; i<k; ++i) {
        cin>>a[i];
        dp[1<<i][a[i]]=0;
    }
    for (int i=0; i<m; ++i) {
        int a,b,w;
        cin>>a>>b>>w;
        adj[a].push_back(pii(b,w));
        adj[b].push_back(pii(a,w));
    }

    for (int bit=1; bit<(1<<k); ++bit) {
        for (int j=0; j<k; ++j) {
            if (!bit&(1<<j)) continue;
            for (int i=1; i<=n; ++i) dp[bit][i]=min(dp[bit][i],dp[(1<<j)][i]+dp[bit^(1<<j)][i]);
        }
        dij(dp[bit]);
    }

    ll ans=LLONG_MAX;
    for (int i=1; i<=n; ++i) ans=min(ans,dp[(1<<k)-1][i]);
    cout<<ans;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:49:17: warning: suggest parentheses around operand of '!' or change '&' to '&&' or '!' to '~' [-Wparentheses]
   49 |             if (!bit&(1<<j)) continue;
      |                 ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 55252 KB Output is correct
2 Correct 21 ms 55232 KB Output is correct
3 Correct 21 ms 55308 KB Output is correct
4 Correct 23 ms 55244 KB Output is correct
5 Correct 24 ms 55252 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 72380 KB Output is correct
2 Correct 498 ms 71712 KB Output is correct
3 Correct 334 ms 64196 KB Output is correct
4 Correct 81 ms 64356 KB Output is correct
5 Correct 345 ms 72176 KB Output is correct
6 Correct 96 ms 64308 KB Output is correct
7 Correct 27 ms 55380 KB Output is correct
8 Correct 26 ms 55448 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 55372 KB Output is correct
2 Correct 29 ms 55500 KB Output is correct
3 Correct 28 ms 55364 KB Output is correct
4 Correct 28 ms 55488 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 72184 KB Output is correct
2 Correct 1106 ms 74644 KB Output is correct
3 Correct 763 ms 66372 KB Output is correct
4 Correct 565 ms 72528 KB Output is correct
5 Correct 184 ms 68744 KB Output is correct
6 Correct 92 ms 69488 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1935 ms 72280 KB Output is correct
2 Correct 2003 ms 75136 KB Output is correct
3 Correct 1907 ms 74624 KB Output is correct
4 Correct 1261 ms 66388 KB Output is correct
5 Correct 1008 ms 72436 KB Output is correct
6 Correct 244 ms 68944 KB Output is correct
7 Correct 102 ms 69796 KB Output is correct