记录编号	466377	评测结果	WAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2014]魔法森林	最终得分	95
用户昵称	BaDBoY	是否通过	未通过
代码语言	C++	运行时间	1.282 s
提交时间	2017-10-28 20:42:14	内存使用	82.00 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int read() {
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') {
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	return s*f;
}
int r[50005],tot,bian[100005],size;
struct edge {
	int to,next,a,b;
} c[200005];
struct node {
	int x,y,a,b;
	friend bool operator < (node xx,node yy) {
		return xx.a<yy.a;
	}
} code[100005];
void add(int x,int y,int a,int b) {
	c[tot]=(edge) {
		y,r[x],a,b
	};
	r[x]=tot++;
}
int n,m,head,tail,queue[20000005],dis[50005];
bool flag[50005];
void spfa() {
	while(head<tail) {
		int u=queue[++head];
		flag[u]=false;
		for(int i=r[u]; ~i; i=c[i].next) {
			if(dis[c[i].to]>max(dis[u],c[i].b)) {
				dis[c[i].to]=max(dis[u],c[i].b);
				if(!flag[c[i].to]) {
					flag[c[i].to]=true;
					queue[++tail]=c[i].to;
				}
			}
		}
	}
	return ;
}
int ans=0x7fffffff;
int main() {
	freopen("magicalforest.in","r",stdin);
	freopen("magicalforest.out","w",stdout);
	n=read();
	m=read();
	memset(r,-1,sizeof(r));
	memset(dis,0x6f,sizeof(dis));
	for(int x,y,a,b,i=1; i<=m; i++) {
		code[i]=(node) {
			x=read(),y=read(),
			a=read(),b=read()
		};
		bian[i]=a;
	}
	size=unique(bian+1,bian+m+1)-bian-1;
	sort(bian+1,bian+size+1);
	sort(code+1,code+m+1);
	int i=1,j=1;
	dis[1]=0;
	for( ; i<=size; i++) {
		head=tail=0;
		//memset(flag,0,sizeof(flag));
		for( ; j<=m; j++) {
			if(bian[i]==code[j].a) {
				//cout<<i<<" "<<j<<endl;
				int x=code[j].x,y=code[j].y,a=code[j].a,b=code[j].b;
				add(x,y,a,b);
				add(y,x,a,b);
				queue[++tail]=x;
				queue[++tail]=y;
				flag[x]=flag[y]=true;
			}
			if(code[j].a>bian[i]) {
				//j--;
				break;
			}
		}
		spfa();
		ans=min(ans,dis[n]+bian[i]);
	}
	/*for(int i=1; i<=n; i++) {
		cout<<dis[i]<<endl;
	}*/
	/*if(ans==1869574000){
		cout<<"-1";
		return 0;
	}*/
	cout<<ans;
	return 0;
}