oj.uz

Submission #563340

# Submission time Handle Problem Language Result Execution time Memory
563340 2022-05-17T00:44:07 Z abcvuitunggio Cities (BOI16_cities) C++17
100 / 100
 2531 ms 49800 KB 
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const ll mx=1000000000000000001;
ll l[100001],dp[100001][32],res=mx;
int n,m,k,a[100001],u,v,w;
vector <pair <ll, int> > ke[100001];
void dijkstra(){
    priority_queue <pair <ll, int>, vector <pair <ll, int> >, greater <pair <ll, int> > > q;
    for (int i=1;i<=n;i++)
        q.push({l[i],i});
    while (!q.empty()){
        int u=q.top().second;
        ll 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});
            }
    }
}
int 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++)
            if ((mask&i)==i)
                for (int l=1;l<=n;l++)
                    dp[l][mask]=min(dp[l][mask],dp[l][i]+dp[l][mask^i]);
        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 2680 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 2644 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 666 ms 49584 KB Output is correct
2 Correct 634 ms 49144 KB Output is correct
3 Correct 436 ms 39484 KB Output is correct
4 Correct 65 ms 15432 KB Output is correct
5 Correct 357 ms 49620 KB Output is correct
6 Correct 61 ms 15396 KB Output is correct
7 Correct 4 ms 3028 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3144 KB Output is correct
2 Correct 6 ms 3144 KB Output is correct
3 Correct 5 ms 3028 KB Output is correct
4 Correct 5 ms 2948 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1182 ms 49720 KB Output is correct
2 Correct 1144 ms 49180 KB Output is correct
3 Correct 846 ms 39580 KB Output is correct
4 Correct 629 ms 34076 KB Output is correct
5 Correct 189 ms 19540 KB Output is correct
6 Correct 74 ms 17544 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2508 ms 49800 KB Output is correct
2 Correct 2531 ms 49736 KB Output is correct
3 Correct 2413 ms 49168 KB Output is correct
4 Correct 1802 ms 39604 KB Output is correct
5 Correct 1315 ms 34028 KB Output is correct
6 Correct 261 ms 19808 KB Output is correct
7 Correct 85 ms 17804 KB Output is correct