记录编号	120275	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2014]魔法森林	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	5.690 s
提交时间	2014-09-15 21:36:21	内存使用	1.13 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <iterator>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct adj
{
  int to,A,B;
  adj (int to=0,int A=0,int B=0):to(to),A(A),B(B){};
};
struct node
{
  int to,dist;
  node (int to=0,int dist=0):to(to),dist(dist){}
  bool operator <(const node &rhs) const
  {
    return dist>rhs.dist;
  }
};
//==============var declaration=================
const int MAXN=50010;
vector <adj> Edge[MAXN];
int m,n,high=0,low=INF,m1,m2;
int d[MAXN];
bool vis[MAXN];
//==============function declaration============
int visit(int limit);
//==============main code=======================
int main()
{  
  string FileName="magicalforest";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
#ifdef DEBUG  
  system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
  clock_t Start_Time=clock();
#endif    
  scanf("%d%d",&n,&m);
  For(i,1,m)
  {
    int s,e,a,b;
    scanf("%d%d%d%d",&s,&e,&a,&b);
    Edge[s].push_back(adj(e,a,b));
    Edge[e].push_back(adj(s,a,b));
    low=min(b,low),high=max(high,b);
  }
  //通过三分B，找到A+B的最小值
  if (visit(INF)==-1)
  {
    pritnf("-1\n");
    return 0;
  }
  if (high<=30)
  {
    int res=INF;
    For(i,low,high)
    {
      int temp=visit(i);
      if (temp!=-1&&temp+i<res)
        res=temp+i;
    }
    printf("%d\n",res);
    return 0;
  }
  while (low<high)
  {
    m1=(high-low)/3+low;
    m2=(high-low)*2/3+low;
    int cost1=visit(m1);
    int cost2=visit(m2);
    if (cost1+m1>cost2+m2||cost1==-1)
      low=m1+1;
    else
      high=m2;
  }
  pritnf("%d\n",((low+high)/2)+visit((low+high)/2));
#ifdef DEBUG  
  clock_t End_Time=clock();
  printf("\n\nTime Used: %.4lf Ms\n",double(End_Time-Start_Time)/CLOCKS_PER_SEC);
#endif    
  return 0;
}
//================fuction code====================
int visit(int limit)
{
   priority_queue <node> Q;
   int out=0;
   memset(vis,false,sizeof(vis));
   memset(d,-1,sizeof(d));
   d[1]=0;
   Q.push(node(1,0));
   while (!Q.empty()&&out<n)
   {
      node now=Q.top();Q.pop();
      if (vis[now.to])
        continue;
      out++;
      vis[now.to]=true;
      if (now.to==n)
        break;
      int siz=Edge[now.to].size()-1;
      For(i,0,siz)
      {
        adj &e=Edge[now.to][i];
        if (e.B<=limit&&!vis[e.to])
          if (d[e.to]==-1||d[e.to]>max(d[now.to],e.A))
          {
            d[e.to]=max(d[now.to],e.A);
            Q.push(node(e.to,d[e.to]));
          }
      }
   }
   return d[n];
}