Submission #596397

#	Time	Username	Problem	Language	Result	Execution time	Memory
596397		ziduo	Cities (BOI16_cities)	C++14	100 / 100	1923 ms	45008 KiB

cities

#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26