test/queue/RadixHeap-32bit.test.cpp

• View this file on GitHub
• Last update: 2023-06-05 21:57:13+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0596

Depends on

• RadixHeap - 非負整数heap (lib/15-queue/RadixHeap.cpp)

Code

#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;
}

Back to top page