oj.uz

Submission #559939

# Submission time Handle Problem Language Result Execution time Memory
559939 2022-05-11T01:22:25 Z abcvuitunggio Cities (BOI16_cities) C++17
100 / 100
 3378 ms 45648 KB 
#include <iostream>
#include <queue>
#include <vector>
#define int long long
using namespace std;
const int mx=1000000000000000001;
int l[100001],dp[100001][32],n,m,k,a[100001],u,v,w,res=mx;
vector <pair <int, int> > ke[100001];
void dijkstra(){
    priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > q;
    for (int i=1;i<=n;i++)
        q.push({l[i],i});
    while (!q.empty()){
        int u=q.top().second,lu=q.top().first;
        q.pop();
        if (l[u]!=lu)
            continue;
        for (auto v:ke[u])
            if (l[v.first]>l[u]+v.second){
                l[v.first]=l[u]+v.second;
                q.push({l[v.first],v.first});
            }
    }
}
signed main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> k >> m;
    for (int i=1;i<=n;i++){
        l[i]=mx;
        for (int j=0;j<(1<<k);j++)
            dp[i][j]=mx;
    }
    for (int i=0;i<k;i++){
        cin >> a[i];
        dp[a[i]][1<<i]=0;
    }
    for (int i=0;i<m;i++){
        cin >> u >> v >> w;
        ke[u].push_back({v,w});
        ke[v].push_back({u,w});
    }
    for (int mask=0;mask<(1<<k);mask++){
        for (int i=0;i<(1<<k);i++)
            for (int j=0;j<(1<<k);j++)
                if ((i|j)==mask)
                    for (int l=1;l<=n;l++)
                        dp[l][mask]=min(dp[l][mask],dp[l][i]+dp[l][j]);
        for (int i=1;i<=n;i++)
            l[i]=dp[i][mask];
        dijkstra();
        for (int i=1;i<=n;i++)
            dp[i][mask]=l[i];
    }
    for (int i=1;i<=n;i++)
        res=min(res,dp[i][(1<<k)-1]);
    cout << res;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 45356 KB Output is correct
2 Correct 599 ms 45036 KB Output is correct
3 Correct 415 ms 37556 KB Output is correct
4 Correct 70 ms 12156 KB Output is correct
5 Correct 334 ms 45648 KB Output is correct
6 Correct 56 ms 12108 KB Output is correct
7 Correct 5 ms 3156 KB Output is correct
8 Correct 5 ms 3072 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3124 KB Output is correct
2 Correct 7 ms 3076 KB Output is correct
3 Correct 6 ms 3028 KB Output is correct
4 Correct 5 ms 2928 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1382 ms 45496 KB Output is correct
2 Correct 1326 ms 44988 KB Output is correct
3 Correct 1064 ms 37544 KB Output is correct
4 Correct 708 ms 30004 KB Output is correct
5 Correct 157 ms 16016 KB Output is correct
6 Correct 64 ms 14308 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3279 ms 45400 KB Output is correct
2 Correct 3327 ms 45616 KB Output is correct
3 Correct 3378 ms 45228 KB Output is correct
4 Correct 2696 ms 37756 KB Output is correct
5 Correct 1651 ms 30020 KB Output is correct
6 Correct 248 ms 15924 KB Output is correct
7 Correct 76 ms 14596 KB Output is correct