记录编号	200614	评测结果	AAAAAAAAAAAAAAEAAAET
题目名称	2068.Yuyuko	最终得分	85
用户昵称	Skyo	是否通过	未通过
代码语言	C++	运行时间	7.232 s
提交时间	2015-10-29 06:26:17	内存使用	2.09 MiB

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, ans = 1<<30, h[30005], v[100005], nx[100005], w[100005], ot[100005], d[30005];
bool inq[30005];
queue <int> q;

void Initialize()
{
	freopen("zaw.in", "r", stdin);
	freopen("zaw.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++)
	{
		int ui, vi, ai, bi; scanf("%d %d %d %d", &ui, &vi, &ai, &bi);
		int e1 = i*2-1, e2 = i*2;
		nx[e1] = h[ui], h[ui] = e1, v[e1] = vi, w[e1] = ai;
		nx[e2] = h[vi], h[vi] = e2, v[e2] = ui, w[e2] = bi;
		ot[e1] = e2, ot[e2] = e1;
	}
}

int Spfa(int beg, int no)
{
	memset(d, 0x3f, sizeof d);
	memset(inq, 0, sizeof inq);
	while(!q.empty()) q.pop();
	d[beg] = 0;
	q.push(beg);
	while(!q.empty())
	{
		int u = q.front(); q.pop(); inq[u] = 0;
		for(int i = h[u]; i; i = nx[i]) 
		if(i != no && d[v[i]] > d[u] + w[i])
		{
			d[v[i]] = d[u] + w[i];
			if(!inq[v[i]]) {inq[v[i]] = 1; q.push(v[i]);}	
		}	
	} 
	return d[1];
}

int main()
{
	Initialize();
	for(int i = h[1]; i; i = nx[i])
		ans = min(ans, Spfa(v[i], ot[i])+w[i]);
	printf("%d", ans < (int)2e7 ? ans : -1);
	return 0;
}