Submission #247683

#	Time	Username	Problem	Language	Result	Execution time	Memory
247683		kimbj0709	Cities (BOI16_cities)	C++14	100 / 100	2201 ms	46572 KiB

cities

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
#define f first
#define s second
vector<vector<pair<int,int> > > adj(maxn);
#define INT_MAX LLONG_MAX/3
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int no_of_vertex,no_of_special,no_of_edge;
  int input1,input2,input3;
  cin >> no_of_vertex >> no_of_special >> no_of_edge;
  int dist[1<<no_of_special][no_of_vertex+5];
  vector<int> special;
  for(int i=0;i<no_of_special;i++){
    cin >> input1;
    special.push_back(input1);
  }
  for(int i=0;i<no_of_edge;i++){
    cin >> input1 >> input2 >> input3;
    adj[input1].push_back({input2,input3});
    adj[input2].push_back({input1,input3});
  }
  for(int i=0;i<(1<<no_of_special);i++){
    for(int j=0;j<no_of_vertex+5;j++){
      dist[i][j] = INT_MAX;
    }
  }
  for(int i=0;i<no_of_special;i++){
    dist[1<<i][special[i]] = 0;
  }
  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >  q1;
  for(int i=1;i<(1<<no_of_special);i++){
    for(int j=0;j<i;j++){
      if((j|i)!=i){
        continue;
      }
      int comp = i^j;
      for(int a=1;a<=no_of_vertex;a++){
        dist[i][a] = min(dist[i][a],dist[j][a]+dist[comp][a]);
      }
    }
    for(int j=1;j<=no_of_vertex;j++){
      if(dist[i][j]!=INT_MAX){
        q1.push({dist[i][j],j});
      }
    }
    while(q1.size()!=0){
      pair<int,int> a = q1.top();
      q1.pop();
      if(dist[i][a.s]!=a.f){
        continue;
      }
      for(auto k:adj[a.s]){
        if(dist[i][k.f]>a.f+k.s){
          dist[i][k.f] = a.f+k.s;
          q1.push({dist[i][k.f],k.f});
        }
      }
    }
  }
  /*for(int i=0;i<(1<<no_of_special);i++){
    for(int j=1;j<=no_of_vertex;j++){
      cout << dist[i][j] << ' ';
    }
    cout << endl;
  }*/
  int mini = INT_MAX;
  for(int i=1;i<=no_of_vertex;i++){
    //cout << dist[(1<<no_of_special)-1][i] << " ";
    mini = min(mini,dist[(1<<no_of_special)-1][i]);
  }
  cout << mini;
}

Compilation message (stderr)

cities.cpp:8:0: warning: "INT_MAX" redefined
 #define INT_MAX LLONG_MAX/3
 
In file included from /usr/include/c++/7/climits:42:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:39,
                 from cities.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/7/include-fixed/limits.h:120:0: note: this is the location of the previous definition
 #define INT_MAX __INT_MAX__

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26