记录编号	204240	评测结果	AAAAA
题目名称	平凡的皮卡丘	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.291 s
提交时间	2015-11-04 07:44:42	内存使用	1.11 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
const int inf=1061109567;
const int maxn=40010;
const int maxm=100010;
const int mod=998244353;
const double pi=3.14;

struct node1
{
    int to;
    int val;
};

struct node2
{
    int dist1,pos1;
    int dist2,pos2;
    node2() {dist1=dist2=inf;pos1=pos2=0;}
} d[maxn];

vector<node1> G[maxn];

void Swap(int &a,int &b) {int t=a;a=b;b=t;}

bool update(int u,int dist,int pos)
{
    bool flag=false;
    if(d[u].pos1==pos||d[u].pos1==0)
    {
        if(d[u].dist1>dist)
        {
            d[u].dist1=dist;
            d[u].pos1=pos;
            flag=true;
        }
    }
    else if(d[u].pos2==pos|d[u].pos2==0)
    {
        if(d[u].dist2>dist)
        {
            d[u].dist2=dist;
            d[u].pos2=pos;
            flag=true;
        }
    }
    else
    {
        if(d[u].dist1>dist)
        {
            d[u].dist1=dist;
            d[u].pos1=pos;
            flag=true;
        }
        if(d[u].dist2>dist)
        {
            d[u].dist2=dist;
            d[u].pos2=pos;
            flag=true;
        }
    }
    if(d[u].dist2<d[u].dist1)
    {
        Swap(d[u].dist2,d[u].dist1);
        Swap(d[u].pos2,d[u].pos1);
    }
    return flag;
}

void spfa(int st)
{
    queue<int> q;d[st].dist1=0;
    int len=G[st].size();
    for(int i=0;i<len;i++)
    {
        node1 v=G[1][i];
        q.push(v.to);
        d[v.to].dist1=v.val;
        d[v.to].pos1=v.to;
    }
    while(!q.empty())
    {
        int u=q.front();q.pop();
        int len=G[u].size();
        for(int i=0;i<len;i++)
        {
            node1 v=G[u][i];if(v.to==1) continue;
            if(update(v.to,d[u].dist1+v.val,d[u].pos1)||
               update(v.to,d[u].dist2+v.val,d[u].pos2))
            {
                q.push(v.to);
            }
        }
    }
}

int main()
{
    freopen("both.in","r",stdin);
    freopen("both.out","w",stdout);
    //clock_t st=clock();
    int n,m;scanf("%d%d",&n,&m);
    int u,v,w1,w2;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&u,&v,&w1,&w2);
        G[u].push_back((node1){v,w1});
        G[v].push_back((node1){u,w2});
    }
    spfa(1);int ans=inf;
    for(int i=1;i<=n;i++)
    {
        int len=G[i].size(),tmp=inf;
        for(int k=0;k<len;k++)
        {
            node1 v=G[i][k];
            if(v.to==1) tmp=v.val;
        }
        if(d[i].pos1==i)
        {
            tmp+=d[i].dist2;
        }
        else
        {
            tmp+=d[i].dist1;
        }
        ans=min(ans,tmp);
    }
    if(ans==inf) printf("-1\n");
    else printf("%d\n",ans);
    //clock_t ed=clock();
    //printf("\nTime used : %.5lf Ms\n",double(ed-st)/CLOCKS_PER_SEC);
    return 0;
}