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

#include<cstdio>
#include<queue>
#include<deque>
#include<iostream>
using namespace std;
const int SIZEN=40010,INF=0x7fffffff/2;
int N,M;
int T=0;
int pre[SIZEN]={0},f[SIZEN];
deque<pair<int,int> > c[2][SIZEN];
void read()
{
	scanf("%d%d",&N,&M);
	T=N+1;
	int fr,to,c1,c2;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d%d%d",&fr,&to,&c1,&c2);
		c[0][fr].push_back(make_pair(to,c1));
		c[0][to].push_back(make_pair(fr,c2));
	}
}
void dijstra(int t)
{
	priority_queue<pair<int,int> > Q;
	bool inq[SIZEN]={0};
	for(int i=1;i<=T;i++) f[i]=INF;
	inq[1]=1;f[1]=0;Q.push(make_pair(-f[1],1));
	while(!Q.empty())
	{
		int x=Q.top().second;Q.pop();inq[x]=0;
		for(int i=0;i<c[t][x].size();i++)
		{
			int v=c[t][x][i].first,w=c[t][x][i].second;
			if(f[v]>f[x]+w)
			{
				if(x==1) pre[v]=v;
				else pre[v]=pre[x];
				f[v]=f[x]+w;
				if(!inq[v])
				{
					inq[v]=1;
					Q.push(make_pair(-f[v],v));
				}
			}
		}
	}
}
void make_gragh()
{
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<c[0][i].size();j++)
		{
			int v=c[0][i][j].first,w=c[0][i][j].second;
			if(i==1)
			{
				if(pre[v]==v) continue;
				else c[1][i].push_back(make_pair(v,w));
			}
			else if(v==1)
			{
				if(pre[i]==i) c[1][i].push_back(make_pair(T,w));
				else c[1][1].push_back(make_pair(T,w+f[i]));
			}
			else
			{
				if(pre[i]==pre[v]) c[1][i].push_back(make_pair(v,w));
				else c[1][1].push_back(make_pair(v,f[i]+w));
			}
		}
	}
}
void work()
{
	dijstra(0);
	//for(int i=1;i<=N;i++) cout<<f[i]<<" "<<pre[i]<<endl;
	make_gragh();
	dijstra(1);
	if(f[T]!=INF)printf("%d",f[T]);
	else printf("-1");
}
int main()
{
	freopen("both.in","r",stdin);
	freopen("both.out","w",stdout);
	read();
	work();
	return 0;
}