This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0596" #include <vector> #include <iostream> #include <array> #include <algorithm> using namespace std; #include "../../lib/15-queue/RadixHeap.cpp" int main(void){ cin.tie(0);ios::sync_with_stdio(false); int N,K; cin >> N >> K; vector<int> C(N),R(N); for(int i = 0; i < N; ++i) cin >> C[i] >> R[i]; vector<vector<int>> edge(N); for(int i = 0; i < K; ++i) { int A,B; cin >> A >> B; A--,B--; edge[A].push_back(B); edge[B].push_back(A); } vector<vector<int>> dp(N,vector<int>(N+1,1<<30)); dp[0][0] = 0; RadixHeap<pair<int,int>, unsigned int> pq({0,0}); pq.push({0,{0,0}}); while(pq.size()){ auto p = pq.pop(); int from = p.second.first; int r = p.second.second; if(r){ for(int to:edge[from]){ if(dp[to][r-1]>dp[from][r]){ dp[to][r-1]=dp[from][r]; pq.push({dp[to][r-1],{to,r-1}}); } } } if(dp[from][R[from]]>dp[from][r]+C[from]){ dp[from][R[from]]=dp[from][r]+C[from]; pq.push({dp[from][R[from]],{from,R[from]}}); } } cout << *min_element(dp[N-1].begin(),dp[N-1].end()) << endl; return 0; }
#line 1 "test/queue/RadixHeap-32bit.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0596" #include <vector> #include <iostream> #include <array> #include <algorithm> using namespace std; #line 1 "lib/15-queue/RadixHeap.cpp" /* * @title RadixHeap - 非負整数heap * @docs md/queue/RadixHeap.md */ template<class T, class Key = unsigned long long> class RadixHeap{ using TypeNode = pair<Key, T>; template<class InnerKey, class ZZ=InnerKey> class Inner{}; template<class InnerKey> class Inner<InnerKey, unsigned long long>{ array<vector<TypeNode>,65> vq; unsigned long long size_num; TypeNode last; inline int bit(unsigned long long a) { return a ? 64 - __builtin_clzll(a) : 0;} public: Inner(T mini) : size_num(0), last(make_pair(0, mini)) {} inline bool empty() { return size_num == 0; } inline size_t size(){ return size_num; } inline void push(TypeNode x){ ++size_num; vq[bit(x.first^last.first)].push_back(x);} inline void emplace(unsigned long long key,T val){ ++size_num; vq[bit(key^last.first)].emplace_back(key,val);} inline TypeNode pop() { if(vq[0].empty()) { int i = 1; while(vq[i].empty()) ++i; last = *min_element(vq[i].begin(),vq[i].end()); for(auto &p : vq[i]) vq[bit(p.first ^ last.first)].push_back(p); vq[i].clear(); } --size_num; auto res = vq[0].back(); vq[0].pop_back(); return res; } }; template<class InnerKey> class Inner<InnerKey, unsigned int>{ array<vector<TypeNode>,33> vq; unsigned int size_num; TypeNode last; inline int bit(unsigned int a) { return a ? 32 - __builtin_clz(a) : 0;} public: Inner(T mini) : size_num(0), last(make_pair(0, mini)) {} inline bool empty() { return size_num == 0; } inline size_t size(){ return size_num; } inline void push(TypeNode x){ ++size_num; vq[bit(x.first^last.first)].push_back(x);} inline void emplace(unsigned int key,T val){ ++size_num; vq[bit(key^last.first)].emplace_back(key,val);} inline TypeNode pop() { if(vq[0].empty()) { int i = 1; while(vq[i].empty()) ++i; last = *min_element(vq[i].begin(),vq[i].end()); for(auto &p : vq[i]) vq[bit(p.first ^ last.first)].push_back(p); vq[i].clear(); } --size_num; auto res = vq[0].back(); vq[0].pop_back(); return res; } }; Inner<Key,Key> inner; public: RadixHeap(T mini) : inner(mini) {} inline bool empty() { return inner.empty();} inline size_t size(){ return inner.size();} inline void push(TypeNode x){ inner.push(x);} inline void emplace(unsigned long long key,T val){ inner.emplace(key,val);} inline TypeNode pop() { return inner.pop(); } }; #line 9 "test/queue/RadixHeap-32bit.test.cpp" int main(void){ cin.tie(0);ios::sync_with_stdio(false); int N,K; cin >> N >> K; vector<int> C(N),R(N); for(int i = 0; i < N; ++i) cin >> C[i] >> R[i]; vector<vector<int>> edge(N); for(int i = 0; i < K; ++i) { int A,B; cin >> A >> B; A--,B--; edge[A].push_back(B); edge[B].push_back(A); } vector<vector<int>> dp(N,vector<int>(N+1,1<<30)); dp[0][0] = 0; RadixHeap<pair<int,int>, unsigned int> pq({0,0}); pq.push({0,{0,0}}); while(pq.size()){ auto p = pq.pop(); int from = p.second.first; int r = p.second.second; if(r){ for(int to:edge[from]){ if(dp[to][r-1]>dp[from][r]){ dp[to][r-1]=dp[from][r]; pq.push({dp[to][r-1],{to,r-1}}); } } } if(dp[from][R[from]]>dp[from][r]+C[from]){ dp[from][R[from]]=dp[from][r]+C[from]; pq.push({dp[from][R[from]],{from,R[from]}}); } } cout << *min_element(dp[N-1].begin(),dp[N-1].end()) << endl; return 0; }