记录编号	200585	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2068.Yuyuko	最终得分	100
用户昵称	dashgua	是否通过	通过
代码语言	C++	运行时间	0.317 s
提交时间	2015-10-28 23:26:06	内存使用	3.20 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>

template<class Num>void read(Num &x)
{
    char c; int flag = 1;
    while((c = getchar()) < '0' || c > '9')
        if(c == '-') flag *= -1;
    x = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        x = (x<<3) + (x<<1) + (c-'0');
    x *= flag;
}
template<class Num>void write(Num x)
{
    if(!x) {putchar('0');return;}
    if(x < 0) putchar('-'), x = -x;
    static char s[20];int sl = 0;
    while(x) s[sl++] = x%10 + '0',x /= 10;
    while(sl) putchar(s[--sl]);
}

const int maxn = 3e4 + 50, maxm = 1e5 + 50;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
typedef std::pair<long long,int>  factor;
#define fr first.first
#define to first.second
#define w second

int n, m;

std::pair<std::pair<int, int>,int> edge[maxm << 1];
int cur[maxn], flag[maxn], prev[maxn];
long long dist[maxn];
	
void init()
{
	int u, v, a, b;
	
	read(n), read(m);
	
	for(int i = 1; i <= m; i++)
	{
		read(u), read(v), read(a), read(b);
		edge[i] = std::make_pair(std::make_pair(u, v), a);
		edge[i + m] = std::make_pair(std::make_pair(v, u), b);
	}
	m <<= 1;
	
	std::sort(edge + 1, edge + m + 1);
	
	for(int i = 1; i <= m; i++) cur[edge[i].fr]++;
	for(int i = 1; i <= n; i++) cur[i] += cur[i - 1];
}
long long dijkstra(int S,int T)
{
	static bool hash[maxn];
	std::priority_queue<factor, std::vector<factor>, std::greater<factor> > heap;
	
	for(int i = 1; i <= n; i++)
		dist[i] = LINF, hash[i] = false;
	
	dist[1] = 0, heap.push(std::make_pair(0, 1));
	
	while(!heap.empty())
	{
		int u = heap.top().second;
		heap.pop();
		
		if(hash[u]) continue;
		hash[u] = true;
		
		for(int i = cur[u - 1] + 1; i <= cur[u]; i++)
		{
			int p = edge[i].to;
			
			long long dt = dist[u] + edge[i].w;
			
			if(dt < dist[p])
			{
				dist[p] = dt, prev[p] = (u == 1 ? p : prev[u]);
				heap.push(std::make_pair(dist[p], p));
			}
		}
	}
	
	return dist[T] < LINF ? dist[T] : -1;	
}
void rebuild(int S,int T)
{
	int size = m, u, v;
	
	m = 0, n = T;
	
	for(int i = 1; i <= size; i++)
	{
		u = edge[i].fr, v = edge[i].to;
		
		if(u == S)
		{
			if(prev[v] != v) edge[++m] = std::make_pair(std::make_pair(u, v), edge[i].w);
		}
		else if(v == S)
		{
			if(prev[u] == u) edge[++m] = std::make_pair(std::make_pair(u, T), edge[i].w);
			else edge[++m] = std::make_pair(std::make_pair(S, T), dist[u] + edge[i].w);
		}
		else
		{
			if(prev[u] == prev[v]) edge[++m] = std::make_pair(std::make_pair(u, v), edge[i].w);
			else edge[++m] = std::make_pair(std::make_pair(S, v), dist[u] + edge[i].w);
		}
	}
	
	std::sort(edge + 1, edge + m + 1);
	for(int i = 0; i <= n; i++) cur[i] = 0;
	for(int i = 1; i <= m; i++) cur[edge[i].fr]++;
	for(int i = 1; i <= n; i++) cur[i] += cur[i - 1];
}
void solve()
{
	dijkstra(1, n);
	
	rebuild(1, n + 1);
	
	write(dijkstra(1, n));
}//zhe shi wo sun zi xie de
int main()
{
	freopen("zaw.in","r",stdin);
	freopen("zaw.out","w",stdout);
	
	init();
	
	solve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}