4643100 bjtu1 3253 Accepted 1304K 47MS C++ 1456B 2009-02-18 12:14:46 

#include<stdio.h>
#include<malloc.h>
#include<queue>
#include<vector>
#define MAX  20001
using namespace std;




__int64 min1;
int weight[MAX];


typedef struct Node{
	int w;
	int flag;
	int id;
	struct Node *left,*right;
}Node;
Node T[3*MAX];

struct cmp{
	bool operator()(const Node &e1,const Node &e2){
		return e1.w>e2.w;
	}
};

priority_queue<Node,vector<Node>,cmp>heap;

void huffman(Node T[MAX],int weight[MAX],int n){
	int i;
	Node s1,s2; 
    
	while(heap.size())
		heap.pop();
	for(i=0;i<n;i++){
		T[i].w=weight[i];
		T[i].flag=0;
		T[i].id=i;
		T[i].left=T[i].right=NULL;
		heap.push(T[i]);
	}
	for(;i<2*n-1;i++){
		T[i].id=i;
		T[i].w=T[i].flag=0;
		T[i].left=T[i].right=NULL;
	}
	for(i=n;i<2*n-1;i++){
		s1=heap.top();
		heap.pop();
		s2=heap.top();
		heap.pop();
		T[s1.id].flag=1;
		T[s2.id].flag=1;
		T[i].w=s1.w+s2.w;
		T[i].left=&T[s1.id];
		T[i].right=&T[s2.id];
		if(i!=2*n-2) heap.push(T[i]);
	}
};

void Travel(Node *s,int i){
	if(s==NULL)
		return;
	if(s->left==NULL&&s->right==NULL)
		min1+=(s->w+i);
	else{
		Travel(s->left,i+1);
		Travel(s->right,i+1);
	}
};

int main()
{
	int i;
	int n;
	Node *p;

	while(scanf("%d",&n)!=EOF){
		for(i=0;i<n;i++)
			scanf("%d",&weight[i]);
		huffman(T,weight,n);
		for(i=0;i<2*n-1;i++)
			if(!T[i].flag)
				break;
			min1=0;
			p=&T[i];
			Travel(p,0);
			printf("%I64d\n",min1);
	}

	return 0;
}