记录编号	205049	评测结果	AAAAA
题目名称	平凡的皮卡丘	最终得分	100
用户昵称	Tychus	是否通过	通过
代码语言	C++	运行时间	1.446 s
提交时间	2015-11-04 19:53:46	内存使用	7.22 MiB

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <string>
#include <cmath>
using namespace std;
struct line
{
	int w,y,next;
}e[200050];
int n,m,u,v,c1,c2,linkk[40050],d1[40050],q[1000000],d2[40050],col1[40050],ans=0,col2[40050];
int head=0,tail=0;
bool flag[40050];
void spfa()
{
	d1[1]=0;
	d2[1]=0;
	while (head++<tail)
	{
		for (int i=linkk[q[head]];i;i=e[i].next)
			if (e[i].y!=1)
			{
				int sum1=d1[q[head]]+e[i].w,sum2=d2[q[head]]+e[i].w,tn=q[head],tx=e[i].y;
				bool f=0;
				if (col1[tn]==col1[tx]||col1[tn]==col2[tx])
				{
					if (col1[tn]==col1[tx]&&d1[tx]>sum1) d1[tx]=sum1,f=1;
					if (col1[tn]==col2[tx]&&d2[tx]>sum1) d2[tx]=sum1,f=1;
				}
				else
				if (!col1[tx]||!col2[tx])
				{
					if (!col1[tx]) d1[tx]=sum1,col1[tx]=col1[tn],f=1;
					else d2[tx]=sum1,col2[tx]=col1[tn],f=1;
				}
				else
				{
					if (d1[tx]>sum1) d1[tx]=sum1,col1[tx]=col1[tn],f=1;
					else if (d2[tx]>sum1) d2[tx]=sum1,col2[tx]=col1[tn],f=1;
				}
				if (col2[tn]==col2[tx]||col2[tn]==col2[tx])
				{
					if (col2[tn]==col1[tx]&&d1[tx]>sum2) d1[tx]=sum2,f=1;
					if (col2[tn]==col2[tx]&&d2[tx]>sum2) d2[tx]=sum2,f=1;
				}
				else
				if (!col1[tx]||!col2[tx])
				{
					if (!col1[tx]) d1[tx]=sum2,col1[tx]=col2[tn],f=1;
					else d2[tx]=sum2,col2[tx]=col2[tn],f=1;
				}
				else
				{
					if (d1[tx]>sum2) d1[tx]=sum2,col1[tx]=col2[tn],f=1;
					else if (d2[tx]>sum2) d2[tx]=sum2,col2[tx]=col2[tn],f=1;
				}
				if (f) q[++tail]=tx;
				if (d1[tx]>d2[tx])
				{
					swap(d1[tx],d2[tx]);
					swap(col1[tx],col2[tx]);
				}
			}
		flag[q[head]]=0;
	}
}
void init()
{
	ios::sync_with_stdio(false);
	memset(d1,60,sizeof(d1));
	memset(d2,60,sizeof(d2));
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		cin>>u>>v>>c1>>c2;
		e[2*i-1].y=v;
		e[2*i-1].w=c1;
		e[2*i-1].next=linkk[u];
		linkk[u]=2*i-1;
		e[2*i].y=u;
		e[2*i].w=c2;
		e[2*i].next=linkk[v];
		linkk[v]=2*i;
	}
	for (int i=linkk[1];i;i=e[i].next)
	{
		col1[e[i].y]=e[i].y;
		q[++tail]=e[i].y;
		flag[e[i].y]=1;
		d1[e[i].y]=e[i].w;
	}
}
int main()
{
	freopen("both.in","r",stdin);
	freopen("both.out","w",stdout);
	init();
	spfa();
	for (int i=linkk[1];i;i=e[i].next)
	{
		int temp;
		for (int j=linkk[e[i].y];j;j=e[j].next)
			if (e[j].y==1)
			{
				temp=e[j].w;
				break;
			}
		if (col1[e[i].y]==e[i].y&&d2[e[i].y]&&(temp+d2[e[i].y]<ans||!ans))
			ans=temp+d2[e[i].y];
		if (col1[e[i].y]!=e[i].y&&(d1[e[i].y]+temp<ans||!ans))
			ans=d1[e[i].y]+temp;
	}
	cout<<ans<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}