记录编号	200845	评测结果	AAAAAAAAAAAAAAAAAATT
题目名称	Yuyuko	最终得分	90
用户昵称	irony	是否通过	未通过
代码语言	C++	运行时间	13.286 s
提交时间	2015-10-29 17:02:41	内存使用	0.84 MiB

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct node{
	int to,w;
	node(){}
	node(int b,int c){to=b;w=c;}
	bool operator < (const node &a) const
	{
		if(w==a.w) return to<a.to;
		else return w>a.w;
	}
};
const int maxn=30005;
vector <node> g[maxn];
queue <node> q;
int n,m,ui,vi,ai,bi;
int mark[maxn],d[maxn];
int len=0,ans=1<<27;

void init()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&ui,&vi,&ai,&bi);
		if(ui==1)
		{
			mark[++len]=vi;
			g[1].push_back(node(vi,ai));
		    g[vi].push_back(node(n+1,bi));
		}
		else if(vi==1)
		{
			mark[++len]=ui;
			g[1].push_back(node(ui,bi));
		    g[ui].push_back(node(n+1,ai));
		}
		else
		{
		    g[ui].push_back(node(vi,ai));
		    g[vi].push_back(node(ui,bi));
		}
	}
}

void outit()
{
	if(ans==1<<27) printf("-1");
	else printf("%d",ans);
}

void Dijkstra(int x0)
{
	for(int i=1;i<=n+1;i++)
	    d[i]=1<<27;
	d[1]=0;
	q.push(node(1,0));
	while(!q.empty())
	{
		node t=q.front();
		q.pop();
		int x=t.to;
		for(int i=0;i<g[x].size();i++)
		{
		    
			int y=g[x][i].to;
			
			int w=g[x][i].w;
			if(x==1&&y!=x0) continue;
			if(x==x0&&y==n+1) continue;
			if(d[y]>d[x]+w)
			{
				d[y]=d[x]+w;
				q.push(node(y,d[y]));
			}
		}
	}
	ans=min(ans,d[n+1]);
}	
	
		
void work()
{
	for(int i=1;i<=len;i++)
	{
		Dijkstra(mark[i]);
	}
}
		

int main()
{
	freopen("zaw.in","r",stdin);
	freopen("zaw.out","w",stdout);
	init();
	work();
	outit();
}