记录编号	201207	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	Yuyuko	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.211 s
提交时间	2015-10-30 11:12:28	内存使用	15.68 MiB

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