记录编号	436122	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2014]魔法森林	最终得分	100
用户昵称	hunter	是否通过	通过
代码语言	C++	运行时间	1.154 s
提交时间	2017-08-11 07:12:38	内存使用	3.42 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define maxn 50005
using namespace std;
int n,m;
int dis[maxn];
struct edge2
{
    int fr,to,a,b;  
}s[maxn*2];
int kk=0;
struct edge
{
      int to,ne,w;
}b[maxn*2];
int k=0,head[maxn];
bool vis[maxn];
struct node
{
     int id; 
     bool operator <(const node &a)
     const { 
         return dis[id]>dis[a.id];
     }
}tmp,now;
priority_queue<node> q;
void add(int u,int v,int w)
{
     k++;
     b[k].to=v;b[k].ne=head[u];b[k].w=w;head[u]=k;
}
void add2(int u,int v,int a,int b)
{
      kk++;
      s[kk].fr=u;s[kk].to=v;s[kk].a=a;s[kk].b=b;
}
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return x;
}
int cmp(const edge2 &q,const edge2 &w)
{
     return q.a<w.a;
}
void spfa()
{
     int id;
     while(!q.empty()){
         now=q.top();q.pop();
         id=now.id; 
         vis[id]=0;
         for(int i=head[id];i!=-1;i=b[i].ne)
            if(dis[b[i].to]>max(dis[id],b[i].w)){
               dis[b[i].to]=max(dis[id],b[i].w);
               if(!vis[b[i].to]){
                   vis[b[i].to]=1;
                   tmp.id=b[i].to;
                   q.push(tmp);
               }
         }
     }
}
int main()
{
    freopen("magicalforest.in","r",stdin);
    freopen("magicalforest.out","w",stdout);
    memset(head,-1,sizeof(head));
    memset(dis,0x7f,sizeof(dis));
    n=read();m=read();
    int x,y,ai,bi;
    int op;
    int ans=0x7fffffff;
    for(int i=1;i<=m;i++){
       x=read();y=read();ai=read();bi=read();
       add2(x,y,ai,bi);
    }
    sort(s+1,s+m+1,cmp);
    dis[1]=0;vis[1]=1;
    tmp.id=1; q.push(tmp);
    for(int i=1;i<=m;i++){
          op=s[i].a;
          int j=i;
          for(j=i;j<=m;j++)
          if(s[j].a==op){
               add(s[j].fr,s[j].to,s[j].b);
               add(s[j].to,s[j].fr,s[j].b);
               if(!vis[s[j].fr]){
                  vis[s[j].fr]=1;
                  tmp.id=s[j].fr;q.push(tmp);
               }
               if(!vis[s[j].to]){
                  vis[s[j].to]=1;
                  tmp.id=s[j].to;q.push(tmp);
               } 
          }
          else break;
          spfa();
          ans=min(ans,dis[n]+op);
          i=j-1;
    }
    if(ans>1000000000) printf("-1\n");
    else printf("%d",ans);
    return 0;
}