记录编号	203676	评测结果	WWWWW
题目名称	平凡的皮卡丘	最终得分	0
用户昵称	momo123	是否通过	未通过
代码语言	C++	运行时间	0.485 s
提交时间	2015-11-03 14:50:20	内存使用	2.45 MiB

#include<cstring>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
struct edge
{
	int to,dist;
};
vector<edge>p1[50005];
vector<edge>p2[50005];
queue<int>q1;
queue<int>q2;
long long dis1[40005],dis2[40005],dissum[40005];
long long minn=1000000000000;
int m,n,s1,s2,k,t;
bool vis1[40005],vis2[40005];
void addedge(int a,int b,int c,int cc)
{
	p1[a].push_back((edge){b,c});
	p2[a].push_back((edge){b,cc});
}
void spfa1()
{
	memset(dis1,-1,sizeof(dis1));
	dis1[s1]=0;
	q1.push(s1);
	while(!q1.empty())
	{
		k=q1.front();
		q1.pop();
		for(int j=0;j<p1[k].size();j++)
		{
			edge&e=p1[k][j];
			if(dis1[e.to]==-1||dis1[e.to]>dis1[k]+e.dist)
			{
				dis1[e.to]=dis1[k]+e.dist;
				if(!vis1[e.to])
				{
					q1.push(e.to);
					vis1[e.to]=1;
				}
			}
		}
	}
}
void spfa2()
{
	memset(dis2,-1,sizeof(dis2));
	dis2[s2]=0;
	q2.push(s2);
	vis2[s2]=1;
	while(!q2.empty())
	{
		t=q2.front();
		q2.pop();
		for(int j=0;j<p2[t].size();j++)
		{
			edge&e=p2[t][j];
			if(dis2[e.to]==-1||dis2[e.to]>dis2[t]+e.dist)
			{
				dis2[e.to]=dis2[t]+e.dist;
				if(!vis2[e.to])
				{
					q2.push(e.to);
					vis2[e.to]=1;
				}
			}
		}
	}
}
int main()
{
	freopen("both.in","r",stdin);
	freopen("both.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,c1,c2;
		cin>>u>>v>>c1>>c2;
		addedge(u,v,c1,c2);
	}
	s1=s2=1;
	spfa1();
	spfa2();
	for(int i=2;i<=n;i++)
	{
		dissum[i]=dis1[i]+dis2[i];
		if(dissum[i]<minn)
		     minn=dissum[i];
	}
	cout<<minn;
}