记录编号	203704	评测结果	AAAAA
题目名称	平凡的皮卡丘	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.323 s
提交时间	2015-11-03 15:18:34	内存使用	2.64 MiB

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define N 40010
using namespace std;
ifstream in("both.in");
ofstream out("both.out");
int n,m;
vector<int> G[N],C[N];
vector<int> F[N],B[N];
bool l[N]={0};
int f[N]={0},p[N]={0},g[N]={0};
int ans,INF=(1<<29);
void add(int u,int v,int w)
{
	F[u].push_back(v);
	B[u].push_back(w);
}
void add2(int u,int v,int w)
{
	G[u].push_back(v);
	C[u].push_back(w);
}
void SPFA(int s)
{
	int i,u,v,w;
	queue<int> q;
	for(i=1;i<=n+5;i++)
	{
		f[i]=INF;
		l[i]=0;
	}
	f[s]=0;
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		l[u]=0;
		for(i=0;i<G[u].size();i++)
		{
			v=G[u][i];
			w=C[u][i];
			if(f[v]>f[u]+w)
			{
				f[v]=f[u]+w;
				if(u==1)p[v]=v;
				else p[v]=p[u];
				if(!l[v])
				{
					l[v]=1;
					q.push(v);
				}
			}
		}
	}
}
void SPFA2(int s)
{
	int i,u,v,w;
	queue<int> q;
	for(i=1;i<=n+5;i++)
	{
		g[i]=INF;
		l[i]=0;
	}
	g[s]=0;
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		l[u]=0;
		for(i=0;i<F[u].size();i++)
		{
			v=F[u][i];
			w=B[u][i];
			if(g[v]>g[u]+w)
			{
				g[v]=g[u]+w;
				if(!l[v])
				{
					l[v]=1;
					q.push(v);
				}
			}
		}
	}
}
void work()
{
	int i,j,u,v,w;
	int S=1,T=n+1;
	SPFA(1);
	for(i=1;i<=n;i++)
	{
		for(j=0;j<G[i].size();j++)
		{
			v=G[i][j];
			w=C[i][j];
			if(i==1)
			{
				if(p[v]==v)continue;
				else add(i,v,w);
			}
			else if(v==1)
			{
				if(p[i]==i)add(i,T,w);
				else add(1,T,f[i]+w);
			}
			else
		    {
				if(p[i]==p[v])add(i,v,w);
				else add(1,v,f[i]+w);
			}
		}
	}
	/*for(i=1;i<=n;i++)
	{
		u=i;
		for(j=0;j<F[i].size();j++)
		{
			v=F[i][j];
			w=B[i][j];
			out<<u<<' '<<v<<' '<<w<<endl;
		}
	}*/
	SPFA2(1);
	ans=g[n+1];
	if(ans==INF)out<<-1<<endl;
	else out<<ans<<endl;
}
void read()
{
	int i,a,b,c,d;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>a>>b>>c>>d;
		add2(a,b,c);
		add2(b,a,d);
		//out<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
	}
}
int main()
{
	read();
	work();
	return 0;
}