oj.uz

Submission #596397

# Submission time Handle Problem Language Result Execution time Memory
596397 2022-07-14T16:59:27 Z ziduo Cities (BOI16_cities) C++14
100 / 100
 1923 ms 45008 KB 
#include<bits/stdc++.h>
using namespace std;
int n, m, k, must[7];
vector<pair<int, int>> edges[100000];
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  cin >>n>>k>>m;
  long long dp[(1<<k)][n];
  for(int i=0; i<(1<<k); i++)
    for(int j=0; j<n; j++)
        dp[i][j] = 100000000000000000LL;
    
  
  for(int i=0; i<k; i++){
    int v;
    cin >> v;
    v--;
    dp[1<<i][v] = 0;
  }
  for(int i=0; i<m; i++){
    int a,b,c;
    cin>>a>>b>>c;
    edges[a-1].push_back({b-1,c});
    edges[b-1].push_back({a-1,c});
  }
  for(int i=1; i<(1<<k); i++){
    for(int j=0; j<i; j++){
        if((i|j)!=i)continue;
        for(int v=0; v<n; v++)
            dp[i][v] = min(dp[i][v], dp[j][v]+dp[i^j][v]);
    }
    priority_queue<pair<long long, int>> que;
    bool visit[n];
    for(int i=0; i<n; i++)visit[i] = false;
    for(int j=0; j<n; j++)
        if(dp[i][j]!=1000000000000000000LL)
            que.push({-dp[i][j], j});
    while(!que.empty()){
        pair<long long, int> q = que.top(); que.pop();
        if(visit[q.second])continue;
        visit[q.second]=true;
        for(auto p: edges[q.second]){
            if(dp[i][p.first]>-q.first+p.second){
               dp[i][p.first]= -q.first+p.second;
               que.push({-dp[i][p.first], p.first});
            }
        }
    }
  }
    long long ans = 1000000000000000000LL;
    for(int i=0; i<n; i++)
        ans = min(ans, dp[(1<<k)-1][i]);
    cout<<ans<<endl;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 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 497 ms 26024 KB Output is correct
2 Correct 502 ms 26032 KB Output is correct
3 Correct 291 ms 17880 KB Output is correct
4 Correct 65 ms 10904 KB Output is correct
5 Correct 307 ms 22824 KB Output is correct
6 Correct 54 ms 10804 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2900 KB Output is correct
2 Correct 6 ms 2940 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 999 ms 32400 KB Output is correct
2 Correct 923 ms 32312 KB Output is correct
3 Correct 635 ms 24280 KB Output is correct
4 Correct 517 ms 22552 KB Output is correct
5 Correct 164 ms 14116 KB Output is correct
6 Correct 60 ms 12596 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1883 ms 45008 KB Output is correct
2 Correct 1896 ms 44836 KB Output is correct
3 Correct 1923 ms 44848 KB Output is correct
4 Correct 1248 ms 36700 KB Output is correct
5 Correct 938 ms 28960 KB Output is correct
6 Correct 214 ms 15384 KB Output is correct
7 Correct 74 ms 12664 KB Output is correct