记录编号	203670	评测结果	AAAAA
题目名称	平凡的皮卡丘	最终得分	100
用户昵称	321Rain	是否通过	通过
代码语言	C++	运行时间	0.297 s
提交时间	2015-11-03 14:41:26	内存使用	11.44 MiB

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 101000
#define MAXC 401000
using namespace std;
struct Node{int from,to,next,data;}edge[MAXN<<1],N_edge[MAXN<<1];
int head[MAXC],f[MAXC],pre[MAXC];
bool vis[MAXC];
int edgenum,N_edgenum;
int n,m;
inline void add(int x,int y,int data){
	edgenum++;
	edge[edgenum].next=head[x];
	edge[edgenum].to=y;
	edge[edgenum].data=data;
	head[x]=edgenum;
	return ;
}
inline void spfa(void){
	memset(f,0x7f7f7f7f,sizeof f);
	memset(vis,0,sizeof vis);
	queue<int> q;
	q.push(1);
	vis[1]=1;
	f[1]=0;
	while(!q.empty()){
		int fr=q.front();
		q.pop();
		vis[fr]=0;
		for(int i=head[fr];i!=-1;i=edge[i].next){
			int to=edge[i].to;
			if(f[to]>f[fr]+edge[i].data){
				f[to]=f[fr]+edge[i].data;
				if(fr==1)
					pre[to]=to;
				else
					pre[to]=pre[fr];
				if(!vis[to]){
					vis[to]=1;
					q.push(to);
				}
			}
		}
	}return ;
}
inline void N_add(int x,int y,int data){
	N_edgenum++;
	N_edge[N_edgenum].from=x;
	N_edge[N_edgenum].to=y;
	N_edge[N_edgenum].data=data;
	return ;
} 
int main(){
	freopen("both.in","r",stdin);
	freopen("both.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof head);
	for(int i=0,u,v,w,y;i<m;i++){
		scanf("%d%d%d%d",&u,&v,&w,&y);
		add(u,v,w);
		add(v,u,y);
	}spfa();
	for(int i=1;i<=n;i++){
		for(int j=head[i];j!=-1;j=edge[j].next){
			int to=edge[j].to;
			if(to==1){
				if(pre[i]!=i)
					N_add(1,n+1,edge[j].data+f[i]);
				else
					N_add(i,n+1,edge[j].data);
			}else{
				if(i==1){
					int vv=edge[j].to;
					if(pre[vv]==vv)
						continue ;
					N_add(1,vv,edge[j].data);
				}else{
					int vv=edge[j].to;
					if(pre[i]==pre[vv])
						N_add(i,vv,edge[j].data);
					else
						N_add(1,vv,f[i]+edge[j].data);
				}
			}
		}
	}edgenum=0;
	memset(head,-1,sizeof head);
	for(int i=1;i<=N_edgenum;i++){
		add(N_edge[i].from,N_edge[i].to,N_edge[i].data);
	}spfa();
	int ans=f[n+1];
	if(ans==0x7f7f7f7f)
		ans=-1;	
	printf("%d",ans);
	return 0;
}