1685. [NOI2014]魔法森林

╰半夏微凉° 2021-09-30 05:38 278阅读 0赞

#                                              [1685. \[NOI2014\]魔法森林][1685. _NOI2014] #

![947305-20170911180739375-1012619362.png][]

![947305-20170911180754203-2138830142.png][]

![947305-20170911180804610-492159081.png][]

![947305-20170911180814453-436842420.png][]

动态SPFA

求两个数的 最优值 我们可以限定一个值 求另一个的最优值

这个题 我们可以 对a排序

每次动态加边

就省去了 每次SPFA的dis和vis数组的清空

cogs上毫无压力 但是在UOJ上有一个额外的测试点 好像专门卡SPFA

毕竟这个正解应该是LCT嘛

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <cctype>
     2 #include <cstdio>
     3 #include <algorithm>
     4 #define max(a,b) a<b?b:a
     5 
     6 const int INF=0x3f3f3f3f;
     7 const int MAXN=50010;
     8 
     9 int n,m,ans;
    10 
    11 int dis[MAXN],vis[MAXN],q[10000000],id[MAXN];
    12 
    13 struct data {
    14     int u,v;
    15     int a,b;
    16     friend bool operator < (data x,data y) {
    17         return x.a<y.a;
    18     }
    19 };
    20 data p[MAXN<<1];
    21 
    22 struct node {
    23     int to;
    24     int a,b;
    25     int next;
    26     node() {}
    27     node(int to,int a,int b,int next):to(to),a(a),b(b),next(next) {}
    28 };
    29 node Edge[MAXN<<2];
    30 
    31 int head[MAXN],tot;
    32 
    33 inline void read(int&x) {
    34     int f=1;register char c=getchar();
    35     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
    36     for(;isdigit(c);x=x*10+c-48,c=getchar());
    37     x=x*f;
    38 }
    39 
    40 inline void swap(int&a,int&b) {
         int t=a;a=b;b=t;}
    41 
    42 inline void add(int x,int y,int a,int b) {
    43     Edge[++tot]=node(y,a,b,head[x]);
    44     head[x]=tot;
    45     Edge[++tot]=node(x,a,b,head[y]);
    46     head[y]=tot;
    47 }
    48 
    49 int hh() {
    50     freopen("magicalforest.in","r",stdin);
    51     freopen("magicalforest.out","w",stdout);
    52     read(n);read(m);
    53     for(int i=1;i<=m;++i) read(p[i].u),read(p[i].v),read(p[i].a),read(p[i].b);
    54     std::sort(p+1,p+1+m);
    55     for(int i=2;i<=n;++i) dis[i]=INF;
    56     ans=INF;
    57     for(int i=1;i<=m;++i) {
    58         add(p[i].u,p[i].v,p[i].a,p[i].b);
    59         int h=0,tail=2;
    60         q[1]=p[i].u;
    61         q[2]=p[i].v;
    62         vis[q[1]]=i;
    63         vis[q[2]]=i;
    64         while(h<tail) {
    65             int u=q[++h];
    66             vis[u]=0;
    67             for(int j=head[u];j;j=Edge[j].next) {
    68                 int v=Edge[j].to;
    69                 int t=max(dis[u],Edge[j].b);
    70                 if(dis[v]>t) {
    71                     dis[v]=t;
    72                     if(vis[v]!=i) q[++tail]=v,vis[v]=i;
    73                 }
    74             }
    75         }
    76         if(p[i].a+dis[n]<ans) ans=p[i].a+dis[n];
    77     }
    78     if(ans==INF) printf("-1\n");
    79     else printf("%d\n",ans);
    80     return 0;
    81 } 
    82 
    83 int sb=hh();
    84 int main(int argc,char**argv) {;}

代码

转载于:https://www.cnblogs.com/whistle13326/p/7506283.html

[1685. _NOI2014]: http://www.cogs.pro/cogs/problem/problem.php?pid=1685
[947305-20170911180739375-1012619362.png]: /images/20210725/ea127b96aa4e49a387a3667cd6c6989f.png
[947305-20170911180754203-2138830142.png]: /images/20210725/0b7faf8d889c4a1c972b9b87ef97c9bd.png
[947305-20170911180804610-492159081.png]: /images/20210725/44b50fd078d042bfadd32943efacaa58.png
[947305-20170911180814453-436842420.png]: /images/20210725/51e85e8c97064500b12445e86641272a.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/00819a8567a04e11bcb0618892882064.png