pku1724source.cpp

包含一个HEAP类的完整实现 以及在PFS算法中的应用

#include<iostream>
#include<fstream>
using namespace std;


struct node{
long cost;
int index;
long dis;
};

#define INF 10000000
long cost[110][110];
long dist[110][110];
void ini(int n)
{
	int i,j;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			cost[i][j]=INF;
			dist[i][j]=INF;
		}
	}
}

int  floyd( int  n)
  {
     int   i, j, k;

     for  (k = 1 ; k <= n; k ++ )
      {
         for  (i = 1 ; i <= n; i ++ )
             for  (j = 1 ; j <= n; j ++ )
              {
                 if  (cost[i][k]  <  INF  &&  cost[k][j]  <  INF
                 &&  cost[i][k]  +  cost[k][j]  < cost[i][j])
                    cost[i][j]  = cost[i][k]  + cost[k][j];
            } 
    } 

     return   0 ;
}


int  floyd2( int  n)
  {
     int   i, j, k;

     for  (k = 1 ; k <= n; k ++ )
      {
         for  (i = 1 ; i <= n; i ++ )
             for  (j = 1 ; j <= n; j ++ )
              {
                 if  (dist[i][k]  <  INF  &&  dist[k][j]  <  INF
                 &&  dist[i][k]  +  dist[k][j]  < dist[i][j])
                    dist[i][j]  = dist[i][k]  + dist[k][j];
            } 
    } 

     return   0 ;
}

bool cmp(node a,node b){
	return a.dis>b.dis;
}
inline bool leaf(long pos,long size){
	return (pos>=size/2)&&(pos<size);
}
inline long leftchild(long pos){
	return pos*2+1;
}
inline long rightchild(long pos){
	return pos*2+2;
}
inline long parent(long pos){
	return (pos-1)/2;
}


template <class T>
class Heap
{
	private:
		T* array;
		int size;
		int maxsize;
		bool (* cmp)(T,T);
	public:
		long get_size();
		Heap(long n,bool (* fun)(T,T));
		T get_top();
		virtual ~Heap(){delete []array;};
		bool insert(const T& newnode);
		T remove_top();
		void siftup(long pos);
		void siftdown(long lef);
};
template <class T>
long Heap<T>::get_size()
{
	return size;
}

template <class T>
T Heap<T>::get_top(){
	return array[0];
}

template <class T>
Heap<T>::Heap(long n,bool (* fun)(T,T)){
	if(n<=0)
		return;
	size=0;
	maxsize=n;
	cmp=fun;
	array=new T[maxsize];
	long i;
	for(i=size/2-1;i>=0;i--){
		siftdown(i);
	}
}

template <class T>
void Heap<T>::siftup(long pos)
{
	T temp=array[pos];
	long next=pos;
	while(next>0&&cmp(array[parent(next)],temp)){
		array[next]=array[parent(next)];
		next=parent(next);
	}
	array[next]=temp;
}
template <class T>
T Heap<T>::remove_top()
{
	T r,p;
	p=array[0];
	if(size==0)
		return r;
	else
	{
		r=array[0];
		array[0]=array[size-1];
		array[size-1]=r;
		size--;
		if(size>1)
			siftdown(0);
		return p;
	}
}

template <class T>
bool Heap<T>::insert(const T& newnode){
	if(size==maxsize)
		return false;
	array[size++]=newnode;
	siftup(size-1);
	return true;
}

template <class T>
void Heap<T>::siftdown(long lef){
	long i=lef;
	long j=leftchild(i);
	T temp=array[i];
	while(j<size){
		if((j<size-1)&&(cmp(array[j],array[j+1])))
			j++;
		if(cmp(temp,array[j])){
			array[i]=array[j];
			i=j;
			j=leftchild(j);
		}
		else
			break;
	}
	array[i]=temp;
}

struct unit{
int p;
int di;
int toll;
};
unit road[110][10100];

void pfs(int n,long limit)
{


	floyd(n);
	if(cost[1][n]>limit){
		cout<<-1<<endl;
		return;
	}
	floyd2(n);
	if(dist[1][n]>=INF){
		cout<<-1<<endl;
		return;
	}
	Heap<node> heap(3000000,cmp);
	int i;
	for(i=1;i<=road[1][0].p;i++){
		node temp;
		temp.cost=road[1][i].toll;
		temp.dis=road[1][i].di;
		temp.index=road[1][i].p;
		heap.insert(temp);
	}


	while(heap.get_size()!=0){
		node top;
		top=heap.remove_top();
	//	cout<<top.index<<endl;//
		if(top.index==n){
			cout<<top.dis<<endl;
			break;
		}

		int i;
		for(i=1;i<=road[top.index][0].p;i++){
			node temp=top;
			temp.index=road[top.index][i].p;
			temp.cost+=road[top.index][i].toll;
			temp.dis+=road[top.index][i].di;
			if(temp.cost>limit){
				continue;
			}
			heap.insert(temp);
		}
	}
}
int main()
{

//	freopen("input.in","r",stdin);//
	long n,k,r;
	cin>>k>>n>>r;
	long i;
	for(i=1;i<=n;i++){
		road[i][0].p=0;
	}
	ini(n);
	for(i=1;i<=r;i++){
		long s,e,l,t;
		scanf("%ld%ld%ld%ld",&s,&e,&l,&t);
		road[s][0].p++;
		road[s][road[s][0].p].p=e;
		road[s][road[s][0].p].di=l;
		road[s][road[s][0].p].toll=t;
		if(cost[s][e]>t)
			cost[s][e]=t;
		if(dist[s][e]>l)
			dist[s][e]=l;
	}

	/*for(i=1;i<=n;i++){
		long j;
		for(j=1;j<=road[i][0].p;j++){
			cout<<road[i][j].p<<" "<<road[i][j].di<<" "<<road[i][j].toll<<endl;
		}
	}*/

	pfs(n,k);
	return 0;
}