Submission #25439

#TimeUsernameProblemLanguageResultExecution timeMemory
25439majkCities (BOI16_cities)C++14
100 / 100
2769 ms48160 KiB
/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ #ifndef MAJK_LIB #define MAJK_LIB #include <vector> #include <stack> #include <iostream> #include <unordered_map> #include <map> #include <iomanip> #include <set> #include <functional> #include <fstream> #include <algorithm> #include <cassert> #include <cmath> #include <string> #include <sstream> #include <queue> #include <bitset> using namespace std; #define x first #define y second constexpr int MOD = 1000000007; typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned int ui; template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;} template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;} template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;} template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>; template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>; auto fraclt = [](const pii&a,const pii&b) { return (ll)a.x * b.y < (ll)b.x * a.y; }; struct cmpfrac { bool operator()(const pii&a,const pii&b)const { return (ll)a.x * b.y < (ll)b.x * a.y; }}; template <typename T> bool in(T a, T b, T c) { return a <= b && b < c; } int logceil(ll x) {int b=0;while(x){x>>=1;++b;}return b;} namespace std { template<typename T,typename U>struct hash<pair<T,U>>{hash<T>t;hash<U>u;size_t operator()(const pair<T,U>&p)const{return t(p.x)^(u(p.y)<<7);}}; } template<typename T,typename F>T bsh(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){l=m+1;r=m;}else{h=m-1;}}return r;} template<typename T,typename F>T bsl(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){h=m-1;r=m;}else{l=m+1;}}return r;} template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; } template<typename T>class vector2:public vector<vector<T>>{public:vector2(){} vector2(size_t a,size_t b,T t=T()):vector<vector<T>>(a,vector<T>(b,t)){}}; template<typename T>class vector3:public vector<vector<vector<T>>>{public:vector3(){} vector3(size_t a,size_t b,size_t c,T t=T()):vector<vector<vector<T>>>(a,vector<vector<T>>(b,vector<T>(c,t))){}}; template <typename T> struct bounded_priority_queue { inline bounded_priority_queue(ui X) : A(X), B(0) {} inline void push(ui L, T V) { B = max(B, L); A[L].push(V); } inline const T &top() const { return A[B].front(); } inline void pop() { A[B].pop(); while (B > 0 && A[B].empty()) --B; } inline bool empty() const { return A[B].empty(); } inline void clear() { B = 0; for (auto &a: A) a = queue<T>(); } private: vector<queue<T>> A; ui B; }; #endif // #include "../l/mod.h" class BOIA { public: ui N,K,M; vector<ui> I; vector<vector<pair<ui,ll>>> E; ll inf = 1000000000000000000LL; void dijkstra(vector<ll> &C) { minheap<pair<ll,ui>> Q; for (int i = 0; i < N; ++i) { if (C[i] != inf) Q.push({C[i], i}); } while (!Q.empty()) { auto q = Q.top(); Q.pop(); if (C[q.y] < q.x) continue; for (auto v: E[q.y]) { ll c = q.x + v.y; if (C[v.x] > c) { C[v.x] = c; Q.push({c,v.x}); } } } } void solve(istream& cin, ostream& cout) { cin >> N >> K >> M; E.resize(N); I.resize(K); cin >> I; for (ui&i: I) --i; for (ui i = 0; i < M; ++i) { ui a,b,c; cin >> a >> b >> c; --a; --b; E[a].push_back({b,c}); E[b].push_back({a,c}); } vector2<ll> C(1<<K, N, inf); fill(C[0].begin(),C[0].end(),0); for (int i = 0; i < K; ++i) { C[1<<i][I[i]] = 0; } for (int i = 1; i < (1<<K); ++i) { for (int j = 1; j < (1<<K); ++j) { for (int k = 1; k < (1<<K); ++k) { if ((j&k) == 0 & (j|k) == i) { for (int l = 0; l < N; ++l) { C[i][l] = min(C[i][l], C[j][l] + C[k][l]); } } } } dijkstra(C[i]); } cout << *min_element(C.back().begin(), C.back().end()) << endl; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); BOIA solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }

Compilation message (stderr)

cities.cpp: In member function 'void BOIA::dijkstra(std::vector<long long int>&)':
cities.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < N; ++i) {
                     ^
cities.cpp: In member function 'void BOIA::solve(std::istream&, std::ostream&)':
cities.cpp:110:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < K; ++i) {
                     ^
cities.cpp:118:16: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
      if ((j&k) == 0 & (j|k) == i) {
                ^
cities.cpp:119:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int l = 0; l < N; ++l) {
                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...