bzoj3669【NOI2014】魔法森林

題面
一道最短路好題……      

開始和喻隊長讨論了一下，喻隊長一眼切：枚舉ai的上界MAX,每次把ai小于等于MAX的邊加到圖裡，以bi為邊權跑最短路。      

但是，這樣做是O（ai*m）的，妥妥TLE，于是我們想了一些鬼畜剪枝優化常數，然并卵……喻隊長身先士卒（比喻隊長帶頭，走在蒟蒻前面），交了一波，TLE60分。      

後來，看了題解才發現這道題是SPFA的玄學用途——維護動态加邊的圖的最短路！隻此一家，絕無僅有！走過路過千萬不要錯過!于是我們就可以不用打LCT來維護一棵最小生成樹（正解）。      

具體做法其實很簡單，每次距離數組不清零，隻把新加入的邊的兩端點入隊。這樣的複雜度就是O（m）的了（也許吧，畢竟SPFA太玄學了），因為最後加起來相當于對原圖跑一遍SPFA。
%%%%%%%%%%%%%%%喻隊長      

1     #include <algorithm>
 2     #include <iostream>
 3     #include <cstdlib>
 4     #include <cstring>
 5     #include <cstdio>
 6     #include <cmath>
 7     using namespace std;
 8     const int N=50005,M=100005,INF=50005;
 9     int gi(){
10         int str=0;char ch=getchar();
11         while(ch>'9' || ch<'0')ch=getchar();
12         while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
13         return str;
14     }
15     int n,m;
16     struct node{
17         int x,y,dis,dist;
18         bool operator <(const node &pp)const{
19             return dis<pp.dis;
20         }
21     }e[M];
22     int head[N],num=0;
23     struct Lin{
24         int next,to,dis;
25     }a[M<<1];
26     void init(int x,int y,int z){
27         a[++num].next=head[x];
28         a[num].to=y;a[num].dis=z;
29         head[x]=num;
30     }
31     void addedge(int x,int y,int z){
32         init(x,y,z);init(y,x,z);
33     }
34     int t=0,sum=0,q[N*10],mod=N*10,f[N],ans=(INF<<1);bool vis[N],usd[M];
35     bool spfa(int lim){
36         int x,u,tmp;
37         while(t!=sum){
38             t++;if(t==mod)t-=mod;x=q[t];
39             for(int i=head[x];i;i=a[i].next){
40                 u=a[i].to;tmp=a[i].dis>f[x]?a[i].dis:f[x];
41                 if(tmp<f[u]){
42                     f[u]=tmp;
43                     if(!vis[u]){
44                         vis[u]=true;
45                         sum++;if(sum==mod)sum-=mod;q[sum]=u;
46                     }
47                 }
48             }
49             vis[x]=false;
50         }
51         if(f[n]==INF)return false;
52         ans=min(ans,f[n]+lim);
53         return true;
54     }
55     void build(int sta){
56         t=0;sum=0;
57         for(int i=sta;i<=m && e[i].dis==e[sta].dis;i++){
58             addedge(e[i].x,e[i].y,e[i].dist);
59             q[++sum]=e[i].x;q[++sum]=e[i].y;
60             vis[e[i].x]=true;vis[e[i].y]=true;
61             usd[i]=true;
62         }
63     }
64     void work(){
65         n=gi();m=gi();
66         for(int i=1;i<=m;i++)
67             e[i].x=gi(),e[i].y=gi(),e[i].dis=gi(),e[i].dist=gi();
68         sort(e+1,e+m+1);
69         int limiter=e[m].dis;
70         memset(f,127/3,sizeof(f));
71         f[1]=0;
72         for(int i=1;i<=m;i++){
73             if(usd[i])continue;
74             build(i);
75             spfa(e[i].dis);
76         }
77         if(ans==(INF<<1))printf("-1\n");
78         else printf("%d\n",ans);
79     }
80     int main()
81     {
82         work();
83         return 0;
84     }      

喻隊長的小常數代碼,比某蒟蒻快一倍

轉載于:https://www.cnblogs.com/y142857/p/7214678.html