记录编号	326327	评测结果	AAAAEEEEEE
题目名称	零食店	最终得分	40
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	4.360 s
提交时间	2016-10-21 07:23:13	内存使用	0.74 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
struct tree{
#define siz(x) ((x)?((x)->size):(0))
	static const double BAL=0.65;
	static const int maxn=100010;
	struct node{//Scapegoat Tree
		int data,size;
		node *lc,*rc,*prt;
		node(int d):data(d),size(1),lc(NULL),rc(NULL),prt(NULL){}
		inline void refresh(){size=siz(lc)+siz(rc)+1;}
	}*root;
	int data[maxn],cnt;
	tree(){root=NULL;}
	void clear(){
		removetree(root);
		root=NULL;
	}
	void insert(int x){
		node *rt=insert(new node(x));
		if(rt)rebuild(rt);
	}
	void erase(int x){
		node *rt=erase(find(x));
		if(rt)rebuild(rt);
	}
	int rank(int x){
		node *rt=root;
		int ans=0;
		while(rt){
			if(x<=rt->data)rt=rt->lc;
			else{
				ans+=siz(rt->lc)+1;
				rt=rt->rc;
			}
		}
		return ans;
	}
	node *insert(node *x){
		if(!root){
			root=x;
			return NULL;
		}
		node *rt=root;
		for(;;){
			if(x->data<rt->data){
				if(rt->lc)rt=rt->lc;
				else{
					rt->lc=x;
					break;
				}
			}
			else{
				if(rt->rc)rt=rt->rc;
				else{
					rt->rc=x;
					break;
				}
			}
		}
		x->prt=rt;
		x=NULL;
		while(rt){
			rt->refresh();
			if(max(siz(rt->lc),siz(rt->rc))>BAL*rt->size)x=rt;
			rt=rt->prt;
		}
		return x;
	}
	node *find(int x){
		node *rt=root;
		while(rt){
			if(x==rt->data)return rt;
			else if(x<rt->data)rt=rt->lc;
			else rt=rt->rc;
		}
		return NULL;
	}
	node *erase(node *x){
		if(x->lc&&x->rc){
			node *y=findmax(x->lc);
			x->data=y->data;
			return erase(y);
		}
		if(!x->lc&&!x->rc){
			if(x->prt){
				if(x==x->prt->lc)x->prt->lc=NULL;
				else x->prt->rc=NULL;
			}
			else root=NULL;
		}
		else if(x->lc&&!x->rc){
			x->lc->prt=x->prt;
			if(x->prt){
				if(x==x->prt->lc)x->prt->lc=x->lc;
				else x->prt->rc=x->lc;
			}
			else root=x->lc;
		}
		else if(!x->lc&&x->rc){
			x->rc->prt=x->prt;
			if(x->prt){
				if(x==x->prt->lc)x->prt->lc=x->rc;
				else x->prt->rc=x->rc;
			}
			else root=x->rc;
		}
		node *rt=x->prt;
		delete x;
		x=NULL;
		while(rt){
			rt->refresh();
			if(max(siz(rt->lc),siz(rt->rc))>BAL*rt->size)x=rt;
			rt=rt->prt;
		}
		return x;
	}
	void rebuild(node *rt){
		cnt=0;
		zorder(rt);
		node *x=rebuild(1,cnt);
		x->prt=rt->prt;
		if(rt->prt){
			if(rt==rt->prt->lc)rt->prt->lc=x;
			else rt->prt->rc=x;
		}
		else root=x;
		removetree(rt);
	}
	void zorder(node *x){
		if(!x)return;
		zorder(x->lc);
		data[++cnt]=x->data;
		zorder(x->rc);
	}
	node *rebuild(int l,int r){
		if(l>r)return NULL;
		if(l==r)return new node(data[l]);
		int mid=(l+r)>>1;
		node *x=new node(data[mid]);
		x->lc=rebuild(l,mid-1);
		if(x->lc)x->lc->prt=x;
		x->rc=rebuild(mid+1,r);
		if(x->rc)x->rc->prt=x;
		x->refresh();
		return x;
	}
	void removetree(node *x){
		if(!x)return;
		removetree(x->lc);
		removetree(x->rc);
		delete x;
	}
	node *findmax(node *x){
		while(x->rc)x=x->rc;
		return x;
	}
#undef siz
}T;
//using namespace __gnu_pbds;
const int maxn=110,maxe=10010;
//tree<int,null_mapped_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>T;
struct edge{int to,prev,w;}e[maxe<<1];
struct Q{
	int c,d,id;
	Q(int c,int d,int id):c(c),d(d),id(id){}
	bool operator<(const Q &q)const{return c<q.c;}
};
void addedge(int,int,int);
void work(int);
void SPFA(int);
int n,m,k,last[maxn]={0},len=0,w[maxn],t[maxn],rnk[maxn]={0},ans[maxn],dis[maxn];
vector<Q>qu[maxn];
queue<int>q;
bool inq[maxn]={0};
int main(){
#define MINE
#ifdef MINE
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
#endif
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
		t[i]=w[i];
	}
	sort(t+1,t+n+1);
	for(int i=1;i<=n;i++){
		int p=lower_bound(t+1,t+n+1,w[i])-t;
		while(rnk[p])p++;
		rnk[p]=i;
	}
	//for(int i=1;i<=n;i++)printf("%d ",rnk[i]);printf("\n");
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		addedge(x,y,z);
		addedge(y,x,z);
	}
	for(int i=1;i<=k;i++){
		int s,c,d;
		scanf("%d%d%d",&s,&c,&d);
		qu[s].push_back(Q(c,d,i));
	}
	for(int i=1;i<=n;i++)work(i);
	for(int i=1;i<=k;i++)printf("%d\n",ans[i]);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
void addedge(int x,int y,int z){
	e[++len].to=y;
	e[len].w=z;
	e[len].prev=last[x];
	last[x]=len;
}
void work(int x){
	//printf("work(%d)\n",x);
	T.clear();
	memset(dis,63,sizeof(dis));
	dis[x]=0;
	q.push(x);
	SPFA(0);
	/*for(int i=1;i<=n;i++){
		if(dis[i]!=0x3f3f3f3f)printf("%d ",dis[i]);
		else printf("INF ");
	}printf("\n");*/
	vector<Q>&a=qu[x];
	sort(a.begin(),a.end());
	int cnt=a.size(),cur=1;
	for(int i=0;i<cnt;i++){
		//printf("i=%d c=%d d=%d\n",i,a[i].c,a[i].d);
		while(cur<=n&&w[rnk[cur]]<=a[i].c){
			q.push(rnk[cur]);
			inq[rnk[cur]]=true;
			cur++;
		}
		SPFA(a[i].c);
		/*for(int j=1;j<=n;j++){
			if(dis[j]!=0x3f3f3f3f)printf("%d ",dis[j]);
			else printf("INF ");
		}printf("\n");*/
		//ans[a[i].id]=T.order_of_key(a[i].d+1);
		ans[a[i].id]=T.rank(a[i].d+1);
	}
}
void SPFA(int c){
	int x;
	while(!q.empty()){
		x=q.front();
		//assert(q.size()<20);
		q.pop();
		inq[x]=false;
		for(int i=last[x];i;i=e[i].prev)if(dis[e[i].to]>dis[x]+e[i].w){
			if(dis[e[i].to]!=0x3f3f3f3f)T.erase(dis[e[i].to]);
			dis[e[i].to]=dis[x]+e[i].w;
			T.insert(dis[e[i].to]);
			//assert(T.size()<10);
			if(w[e[i].to]<=c&&!inq[e[i].to]){
				inq[e[i].to]=true;
				q.push(e[i].to);
			}
		}
	}
}
/*
5 5 2
1 2 3 4 5
1 2 1
1 3 4
2 3 2
1 4 3
2 5 1
1 1 3
2 1 2
Answer:
2
3
*/
/*
5 6 6
7 2 5 1 6
1 2 1
3 1 2
5 4 4
3 5 1
2 3 2
1 5 3
3 1 10
4 7 9
2 6 3
1 3 1
5 7 3
5 7 4
Answer:
3
4
3
1
3
4
*/
/*
本题询问非常多，而在线的话不是时间不够就是附加信息太多无法维护，因此考虑离线。
把询问按起点分类，然后按照c从小到大依次处理各询问，用平衡树维护点的距离，
每次按照新的c重跑SPFA并更新答案。
本来想用pb_ds...然而可重好像要用less_equal，不太保险啊不敢用...
这个平衡树是从普通平衡树抄过来的......
*/