bzoj3669【NOI2014】魔法森林

题面
一道最短路好题……

开始和喻队长讨论了一下，喻队长一眼切：枚举ai的上界MAX,每次把ai小于等于MAX的边加到图里，以bi为边权跑最短路。

但是，这样做是O（ai*m）的，妥妥TLE，于是我们想了一些鬼畜剪枝优化常数，然并卵……喻队长身先士卒（比喻队长带头，走在蒟蒻前面），交了一波，TLE60分。

后来，看了题解才发现这道题是SPFA的玄学用途——维护动态加边的图的最短路！只此一家，绝无仅有！走过路过千万不要错过!于是我们就可以不用打LCT来维护一棵最小生成树（正解）。

具体做法其实很简单，每次距离数组不清零，只把新加入的边的两端点入队。这样的复杂度就是O（m）的了（也许吧，毕竟SPFA太玄学了），因为最后加起来相当于对原图跑一遍SPFA。
%%%%%%%%%%%%%%%喻队长

     #include <algorithm>

     #include <iostream>

     #include <cstdlib>

     #include <cstring>

     #include <cstdio>

     #include <cmath>

     using namespace std;

     const int N=,M=,INF=;

     int gi(){

         int str=;char ch=getchar();

         while(ch>'' || ch<'')ch=getchar();

         while(ch>='' && ch<='')str=(str<<)+(str<<)+ch-,ch=getchar();

         return str;

     }

     int n,m;

     struct node{

         int x,y,dis,dist;

         bool operator <(const node &pp)const{

             return dis<pp.dis;

         }

     }e[M];

     int head[N],num=;

     struct Lin{

         int next,to,dis;

     }a[M<<];

     void init(int x,int y,int z){

         a[++num].next=head[x];

         a[num].to=y;a[num].dis=z;

         head[x]=num;

     }

     void addedge(int x,int y,int z){

         init(x,y,z);init(y,x,z);

     }

     int t=,sum=,q[N*],mod=N*,f[N],ans=(INF<<);bool vis[N],usd[M];

     bool spfa(int lim){

         int x,u,tmp;

         while(t!=sum){

             t++;if(t==mod)t-=mod;x=q[t];

             for(int i=head[x];i;i=a[i].next){

                 u=a[i].to;tmp=a[i].dis>f[x]?a[i].dis:f[x];

                 if(tmp<f[u]){

                     f[u]=tmp;

                     if(!vis[u]){

                         vis[u]=true;

                         sum++;if(sum==mod)sum-=mod;q[sum]=u;

                     }

                 }

             }

             vis[x]=false;

         }

         if(f[n]==INF)return false;

         ans=min(ans,f[n]+lim);

         return true;

     }

     void build(int sta){

         t=;sum=;

         for(int i=sta;i<=m && e[i].dis==e[sta].dis;i++){

             addedge(e[i].x,e[i].y,e[i].dist);

             q[++sum]=e[i].x;q[++sum]=e[i].y;

             vis[e[i].x]=true;vis[e[i].y]=true;

             usd[i]=true;

         }

     }

     void work(){

         n=gi();m=gi();

         for(int i=;i<=m;i++)

             e[i].x=gi(),e[i].y=gi(),e[i].dis=gi(),e[i].dist=gi();

         sort(e+,e+m+);

         int limiter=e[m].dis;

         memset(f,/,sizeof(f));

         f[]=;

         for(int i=;i<=m;i++){

             if(usd[i])continue;

             build(i);

             spfa(e[i].dis);

         }

         if(ans==(INF<<))printf("-1\n");

         else printf("%d\n",ans);

     }

     int main()

     {

         work();

         return ;

     }

喻队长的小常数代码,比某蒟蒻快一倍

巴特西

bzoj3669【NOI2014】魔法森林

最新文章

热门文章