记录编号	219180	评测结果	AAAAAAAAAA
题目名称	[USACO Nov07] 奶牛跨栏	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.440 s
提交时间	2016-01-13 11:17:44	内存使用	1.02 MiB

#include<cstdio>
#include<cstring>
#include<queue>
#define max(a,b) a>b?a:b
using namespace std;
struct edge{
	int v;
	int h;
	int next;
}lst[30000];
int d[310][310];
int visited[310];
int tail = 1;
int start[310];
void addedge(int from,int to,int _h){
	lst[tail].next = start[from];
	lst[tail].v = to;
	lst[tail].h = _h;
	start[from] = tail++;
}
struct heapnode{
	int v;
	int h;
	bool operator < (const heapnode& a)const{
		return h > a.h;
	}
	heapnode(int _v=0,int _h=0){
		v = _v;
		h = _h;
	}
};
void djs(int s){
	priority_queue<heapnode> heap;
	memset(visited,0,sizeof(visited));
	int pt = start[s];
	while(lst[pt].next!=-1){
		heap.push(heapnode(lst[pt].v,lst[pt].h));
	//	printf("push:%d %d %d\n",s,lst[pt].v,lst[pt].h);
		pt = lst[pt].next;
	}
	while(!heap.empty()){
		while(!heap.empty()&&visited[heap.top().v])heap.pop();
		if(heap.empty())break;
		d[s][heap.top().v] = heap.top().h;
		heapnode tmp = heap.top();
		heap.pop();
		pt = start[tmp.v];
		visited[tmp.v] = true;
	//	printf("d[%d][%d]==%d",s,tmp.v,d[s][tmp.v]);
		while(lst[pt].next!=-1){
			if(d[s][lst[pt].v]==0){
				heap.push(heapnode(lst[pt].v,max(d[s][tmp.v],lst[pt].h)));
		//		printf("push:%d %d %d\n",s,lst[pt].v,max(d[s][tmp.v],lst[pt].h));		
			}
			pt = lst[pt].next;
		}
	}
}
int main(){
	freopen("hurdles.in","r",stdin);
	freopen("hurdles.out","w",stdout);
	int n,m,t;
	scanf("%d %d %d",&n,&m,&t);
	int a,b,c;
	memset(d,0,sizeof(d));
	lst[0].next = -1;
	for(int i = 1;i<=m;++i){
		scanf("%d %d %d",&a,&b,&c);
		addedge(a,b,c);
	}
	for(int i = 1;i<=n;++i)djs(i);
	for(int i = 0;i<t;++i){
		scanf("%d %d",&a,&b);
		if(d[a][b])printf("%d\n",d[a][b]);
		else printf("-1\n");
	}
	
	fclose(stdin);fclose(stdout);
	return 0;
}