首页 > 代码库 > NOI2014 魔法森林
NOI2014 魔法森林
3669: [Noi2014]魔法森林
Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 106 Solved: 62
[Submit][Status]
Description
为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。小E可以借助它们的力量，达到自己的目的。
只要小E带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边Ei包含两个权值Ai与Bi。若身上携带的A型守护精灵个数不少于Ai，且B型守护精灵个数不少于Bi，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小E想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。
Input
第1行包含两个整数N,M，表示无向图共有N个节点，M条边。 接下来M行，第行包含4个正整数Xi,Yi,Ai,Bi，描述第i条无向边。其中Xi与Yi为该边两个端点的标号，Ai与Bi的含义如题所述。 注意数据中可能包含重边与自环。
Output
输出一行一个整数：如果小E可以成功拜访到隐士，输出小E最少需要携带的守护精灵的总个数；如果无论如何小E都无法拜访到隐士，输出“-1”（不含引号）。
Sample Input
【输入样例1】
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17
【输入样例2】
3 1
1 2 1 1
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17
【输入样例2】
3 1
1 2 1 1
Sample Output
【输出样例1】
32
【样例说明1】
如果小E走路径1→2→4，需要携带19+15=34个守护精灵；
如果小E走路径1→3→4，需要携带17+17=34个守护精灵；
如果小E走路径1→2→3→4，需要携带19+17=36个守护精灵；
如果小E走路径1→3→2→4，需要携带17+15=32个守护精灵。
综上所述，小E最少需要携带32个守护精灵。
【输出样例2】
-1
【样例说明2】
小E无法从1号节点到达3号节点，故输出-1。
【样例说明1】
如果小E走路径1→2→4，需要携带19+15=34个守护精灵；
如果小E走路径1→3→4，需要携带17+17=34个守护精灵；
如果小E走路径1→2→3→4，需要携带19+17=36个守护精灵；
如果小E走路径1→3→2→4，需要携带17+15=32个守护精灵。
综上所述，小E最少需要携带32个守护精灵。
【输出样例2】
-1
【样例说明2】
小E无法从1号节点到达3号节点，故输出-1。
HINT
2<=n<=50,000
0<=m<=100,000
1<=ai ,bi<=50,000
Source
题解：
卡时真是一件痛苦的事儿。。考场上肯定卡不出来。。。
考场上怎么就sb的去枚举a，二分b，在spfa呢？更直观的想法不就是枚举a做mst吗？脑袋短路了。。。
正解是LCT，蒟蒻不会，先spfa水过。。
枚举a，做spfa即可，但这样只有30分，考虑各种优化：
1.每次枚举的时候 d 数组不用清空，如果 d[n]值发生了变化，一定走了一条当前枚举的 a 的上限，则每次用 d [n]+xx 来更新答案，如果没发生变化，也不会影响答案，因为xx是递增的
2.如果这样直接做的话会是答案错误，这是为什么？
这是因为在加入了一条新边之后，不一定能更新从 1 出发的点，所以其他点就不会被加入队列，这条边就没用被用到！
所以我们应当在枚举到一条边的时候，将这条边的两端打标记，spfa从这些有标记的点出发即可
3.发现TLE。。。
如果打印出ans的变化值可以发现，在开始很长时间内ans都是 inf，也就是说 1 与 n 都不连通
这样我们可以从小到大加入边，用并查集维护连通性，直到 1 与 n 第一次连通时，我们开始做 spfa，这样可以省掉一些无用的过程
综合以上3点，终于AC。。。
代码：
1.考场35分（真是RP啊。。。）
1 const inf=maxlongint>>2;maxn=100000+10; 2 type node=record 3 from,go,next,v1,v2:longint; 4 end; 5 var a,b,d1,d2,head,fa:array[0..maxn] of longint; 6 q:array[0..10*maxn] of longint; 7 e:array[0..maxn*2] of node; 8 v:array[0..maxn] of boolean; 9 i,j,xx,yy,ll,tot,rr,x,y,point,mid:longint; 10 ans,n,m:int64; 11 function find(x:longint):longint; 12 begin 13 if fa[x]<>x then fa[x]:=find(fa[x]); 14 exit(fa[x]); 15 end; 16 function max(x,y:longint):longint; 17 begin 18 if x>y then exit(x) else exit(y); 19 end; 20 procedure sort1(l,r:longint); 21 var i,j,x,y:longint; 22 begin 23 i:=l;j:=r;x:=a[(i+j)>>1]; 24 repeat 25 while a[i]>x do inc(i); 26 while a[j]<x do dec(j); 27 if i<=j then 28 begin 29 y:=a[i];a[i]:=a[j];a[j]:=y; 30 inc(i);dec(j); 31 end; 32 until i>j; 33 if i<r then sort1(i,r); 34 if j>l then sort1(l,j); 35 end; 36 procedure sort2(l,r:longint); 37 var i,j,x,y:longint; 38 begin 39 i:=l;j:=r;x:=b[(i+j)>>1]; 40 repeat 41 while b[i]<x do inc(i); 42 while b[j]>x do dec(j); 43 if i<=j then 44 begin 45 y:=b[i];b[i]:=b[j];b[j]:=y; 46 inc(i);dec(j); 47 end; 48 until i>j; 49 if i<r then sort2(i,r); 50 if j>l then sort2(l,j); 51 end; 52 procedure insert(x,y,z,w:longint); 53 begin 54 inc(tot); 55 with e[tot] do 56 begin 57 from:=x;go:=y;next:=head[x];head[x]:=tot;v1:=z;v2:=w; 58 end; 59 end; 60 procedure spfa; 61 var i,x,y,h,t,tmp1,tmp2:longint; 62 begin 63 for i:=1 to n do d1[i]:=inf; 64 for i:=1 to n do d2[i]:=inf; 65 fillchar(v,sizeof(v),false); 66 h:=0;t:=1;q[1]:=1;d1[1]:=0;d2[1]:=0; 67 while h<t do 68 begin 69 inc(h); 70 x:=q[h];v[x]:=false; 71 i:=head[x]; 72 while i<>0 do 73 begin 74 y:=e[i].go; 75 tmp1:=max(d1[x],e[i].v1); 76 tmp2:=max(d2[x],e[i].v2); 77 if (tmp1<=xx) and (tmp2<=yy) and (tmp2<d2[y]) then 78 begin 79 d1[y]:=tmp1;d2[y]:=tmp2; 80 if not(v[y]) then 81 begin 82 v[y]:=true; 83 inc(t);q[t]:=y; 84 end; 85 end; 86 i:=e[i].next; 87 end; 88 end; 89 end; 90 procedure init; 91 begin 92 readln(n,m); 93 for i:=1 to n do fa[i]:=i; 94 for i:=1 to m do 95 begin 96 readln(x,y,a[i],b[i]); 97 xx:=find(x);yy:=find(y); 98 if xx<>yy then fa[xx]:=yy; 99 insert(x,y,a[i],b[i]);insert(y,x,a[i],b[i]);100 end;101 sort1(1,m);102 sort2(1,m);103 end;104 procedure work1;105 begin106 xx:=a[1];point:=1;107 while true do108 begin109 ll:=1;rr:=m;110 while ll<rr do111 begin112 mid:=(ll+rr)>>1;113 yy:=b[mid];114 spfa;115 if d2[n]<>inf then rr:=mid else ll:=mid+1;116 end;117 inc(point);118 while (point<=m) and (d1[n]<a[point]) do inc(point);119 if point>m then break;120 xx:=a[point];121 if d1[n]+d2[n]<ans then ans:=d1[n]+d2[n];122 end;123 writeln(ans);124 end;125 procedure work2;126 begin127 for i:=1 to 100 do128 begin129 xx:=random(a[1])+1;130 yy:=random(b[m])+1;131 spfa;132 if d1[n]+d2[n]<ans then ans:=d1[n]+d2[n];133 end;134 writeln(ans);135 end;136 begin137 assign(input,‘forest.in‘);assign(output,‘forest.out‘);138 reset(input);rewrite(output);139 init;140 ans:=inf;141 if find(1)<>find(n) then writeln(‘-1‘) else if n*m*16<50000000 then work1 else work2;142 close(input);close(output);143 end.
2.朴素SPFA55分
1 const inf=maxlongint>>2;maxn=100000+10; 2 type node=record 3 from,go,next,v1,v2:longint; 4 end; 5 var a,b,d1,d2,head,fa:array[0..maxn] of longint; 6 q:array[0..10*maxn] of longint; 7 e:array[0..maxn*2] of node; 8 v:array[0..maxn] of boolean; 9 i,j,xx,yy,l,tot,r,x,y:longint; 10 ans,n,m:int64; 11 function find(x:longint):longint; 12 begin 13 if fa[x]<>x then fa[x]:=find(fa[x]); 14 exit(fa[x]); 15 end; 16 function max(x,y:longint):longint; 17 begin 18 if x>y then exit(x) else exit(y); 19 end; 20 function min(x,y:longint):longint; 21 begin 22 if x<y then exit(x) else exit(y); 23 end; 24 25 procedure sort(l,r:longint); 26 var i,j,x,y:longint; 27 begin 28 i:=l;j:=r;x:=a[(i+j)>>1]; 29 repeat 30 while a[i]<x do inc(i); 31 while a[j]>x do dec(j); 32 if i<=j then 33 begin 34 y:=a[i];a[i]:=a[j];a[j]:=y; 35 inc(i);dec(j); 36 end; 37 until i>j; 38 if i<r then sort(i,r); 39 if j>l then sort(l,j); 40 end; 41 procedure insert(x,y,z,w:longint); 42 begin 43 inc(tot); 44 with e[tot] do 45 begin 46 from:=x;go:=y;next:=head[x];head[x]:=tot;v1:=z;v2:=w; 47 end; 48 end; 49 procedure spfa; 50 var i,x,y,h,t,tmp1,tmp2:longint; 51 begin 52 for i:=1 to n do d1[i]:=inf; 53 for i:=1 to n do d2[i]:=inf; 54 fillchar(v,sizeof(v),false); 55 h:=0;t:=1;q[1]:=1;d1[1]:=0;d2[1]:=0; 56 while h<t do 57 begin 58 inc(h); 59 x:=q[h];v[x]:=false; 60 i:=head[x]; 61 while i<>0 do 62 begin 63 y:=e[i].go; 64 tmp1:=max(d1[x],e[i].v1); 65 tmp2:=max(d2[x],e[i].v2); 66 if (tmp1<=xx) and (tmp2<d2[y]) then 67 begin 68 d1[y]:=tmp1;d2[y]:=tmp2; 69 if not(v[y]) then 70 begin 71 v[y]:=true; 72 inc(t);q[t]:=y; 73 end; 74 end; 75 i:=e[i].next; 76 end; 77 end; 78 end; 79 procedure init; 80 begin 81 readln(n,m); 82 for i:=1 to n do fa[i]:=i; 83 for i:=1 to m do 84 begin 85 readln(x,y,a[i],b[i]); 86 xx:=find(x);yy:=find(y); 87 if xx<>yy then fa[xx]:=yy; 88 insert(x,y,a[i],b[i]);insert(y,x,a[i],b[i]); 89 end; 90 sort(1,m); 91 end; 92 procedure work1; 93 begin 94 xx:=a[1];l:=0;r:=m; 95 while true do 96 begin 97 while a[l]=a[l-1] do inc(l); 98 inc(l);xx:=a[l]; 99 if l>r then break;100 spfa;101 while d1[n]+d2[n]<=a[r] do dec(r);102 ans:=min(ans,d1[n]+d2[n]);103 xx:=a[r];104 spfa;105 ans:=min(ans,d1[n]+d2[n]);106 while d1[n]<=a[r] do dec(r);107 end;108 writeln(ans);109 end;110 begin111 assign(input,‘forest.in‘);assign(output,‘forest.out‘);112 reset(input);rewrite(output);113 init;114 ans:=inf;115 if find(1)<>find(n) then writeln(‘-1‘) else work1;116 close(input);close(output);117 end.
3.MST40分
1 const inf=maxlongint>>2;maxn=100000+10; 2 type node=record 3 from,go,next,v1,v2:longint; 4 end; 5 arr=array[0..maxn] of longint; 6 var a,b,c,d,head,fa,aa:arr; 7 e:array[0..maxn*2] of node; 8 v,hash:array[0..maxn] of boolean; 9 i,j,xx,yy,l,tot,r,x,y,cnt:longint; 10 ans,n,m:int64; 11 flag:boolean; 12 function find(x:longint):longint; 13 begin 14 if fa[x]<>x then fa[x]:=find(fa[x]); 15 exit(fa[x]); 16 end; 17 function max(x,y:longint):longint; 18 begin 19 if x>y then exit(x) else exit(y); 20 end; 21 function min(x,y:longint):longint; 22 begin 23 if x<y then exit(x) else exit(y); 24 end; 25 procedure swap(var x,y:longint); 26 var t:longint; 27 begin 28 t:=x;x:=y;y:=t; 29 end; 30 31 procedure sort(l,r:longint); 32 var i,j,x:longint; 33 begin 34 i:=l;j:=r;x:=aa[(i+j)>>1]; 35 repeat 36 while aa[i]<x do inc(i); 37 while aa[j]>x do dec(j); 38 if i<=j then 39 begin 40 swap(aa[i],aa[j]); 41 inc(i);dec(j); 42 end; 43 until i>j; 44 if i<r then sort(i,r); 45 if j>l then sort(l,j); 46 end; 47 procedure sort1(l,r:longint); 48 var i,j,x:longint; 49 begin 50 i:=l;j:=r;x:=b[(i+j)>>1]; 51 repeat 52 while b[i]<x do inc(i); 53 while b[j]>x do dec(j); 54 if i<=j then 55 begin 56 swap(a[i],a[j]);swap(b[i],b[j]);swap(c[i],c[j]);swap(d[i],d[j]); 57 inc(i);dec(j); 58 end; 59 until i>j; 60 if i<r then sort1(i,r); 61 if j>l then sort1(l,j); 62 end; 63 procedure insert(x,y,z,w:longint); 64 begin 65 inc(tot); 66 with e[tot] do 67 begin 68 from:=x;go:=y;next:=head[x];head[x]:=tot;v1:=z;v2:=w; 69 end; 70 end; 71 procedure init; 72 begin 73 readln(n,m); 74 for i:=1 to n do fa[i]:=i; 75 for i:=1 to m do 76 begin 77 readln(x,y,a[i],b[i]); 78 xx:=find(x);yy:=find(y); 79 if xx<>yy then fa[xx]:=yy; 80 c[i]:=x;d[i]:=y; 81 end; 82 aa:=a; 83 sort(1,m);sort1(1,m); 84 end; 85 procedure dfs(x,t1,t2:longint); 86 var i,y:longint; 87 begin 88 v[x]:=true; 89 if x=n then begin flag:=true;ans:=min(ans,t1+t2);exit;end; 90 i:=head[x]; 91 while i<>0 do 92 begin 93 y:=e[i].go; 94 if not(v[y]) then dfs(y,max(t1,e[i].v1),max(t2,e[i].v2)); 95 if flag then break; 96 i:=e[i].next; 97 end; 98 end; 99 procedure mst;100 var i,j:longint;101 begin102 fillchar(v,sizeof(v),false);103 fillchar(head,sizeof(head),0);tot:=0;104 for i:=1 to n do fa[i]:=i;105 j:=1;106 for i:=1 to n-1 do107 begin108 while (j<=m) and ((a[j]>xx) or (find(d[j])=find(c[j])))do inc(j);109 if j>m then exit;110 fa[find(d[j])]:=find(c[j]);111 insert(c[j],d[j],a[j],b[j]);insert(d[j],c[j],a[j],b[j]);112 end;113 //for i:=1 to n do writeln(head[i]);114 flag:=false;115 dfs(1,0,0);116 end;117 procedure work1;118 begin119 //for i:=1 to m do write(aa[i],‘ ‘);writeln;120 l:=0;r:=m;121 while true do122 begin123 inc(l);124 while aa[l]=aa[l-1] do inc(l);//writeln(l,‘ ‘,aa[l],‘ ‘,r);125 inc(cnt);126 if l>r then break;127 xx:=aa[l];128 mst;129 while ans<=aa[r] do dec(r);130 inc(cnt);131 xx:=aa[r];132 mst;133 dec(r);while aa[r]=aa[r+1] do dec(r);134 end;135 writeln(ans);136 end;137 procedure work2;138 begin139 fillchar(hash,sizeof(hash),false);140 for i:=1 to 200 do141 begin142 repeat143 x:=random(m)+1;144 until not(hash[aa[x]]);145 xx:=aa[x];146 mst;147 end;148 writeln(ans);149 end;150 151 begin152 assign(input,‘forest.in‘);assign(output,‘forest.out‘);153 reset(input);rewrite(output);154 randomize;155 init;156 ans:=inf;157 if find(1)<>find(n) then writeln(‘-1‘)158 else if n*m<20000000 then work1 else work2;159 close(input);close(output);160 end.
4.SPFA优化80分
1 const inf=maxlongint>>2;maxn=100000+10; 2 type node=record 3 from,go,next,v1,v2:longint; 4 end; 5 var a,b,d,c1,c2,head,fa:array[0..maxn] of longint; 6 q:array[0..10*maxn] of longint; 7 e:array[0..maxn*2] of node; 8 v:array[0..maxn] of boolean; 9 i,j,xx,yy,l,z,w,tot,r,x,y:longint; 10 ans,n,m,mm:int64; 11 function find(x:longint):longint; 12 begin 13 if fa[x]<>x then fa[x]:=find(fa[x]); 14 exit(fa[x]); 15 end; 16 function max(x,y:longint):longint; 17 begin 18 if x>y then exit(x) else exit(y); 19 end; 20 function min(x,y:longint):longint; 21 begin 22 if x<y then exit(x) else exit(y); 23 end; 24 procedure swap(var x,y:longint); 25 var t:longint; 26 begin 27 t:=x;x:=y;y:=t; 28 end; 29 30 procedure sort(l,r:longint); 31 var i,j,x:longint; 32 begin 33 i:=l;j:=r;x:=a[(i+j)>>1]; 34 repeat 35 while a[i]<x do inc(i); 36 while a[j]>x do dec(j); 37 if i<=j then 38 begin 39 swap(a[i],a[j]);swap(b[i],b[j]);swap(c1[i],c1[j]);swap(c2[i],c2[j]); 40 inc(i);dec(j); 41 end; 42 until i>j; 43 if i<r then sort(i,r); 44 if j>l then sort(l,j); 45 end; 46 procedure insert(x,y,z,w:longint); 47 begin 48 inc(tot); 49 with e[tot] do 50 begin 51 from:=x;go:=y;next:=head[x];head[x]:=tot;v1:=z;v2:=w; 52 end; 53 end; 54 procedure spfa; 55 var i,x,y,h,t,tmp:longint; 56 begin 57 h:=0;t:=0; 58 for i:=1 to n do if v[i] then begin inc(t);q[t]:=i;end; 59 //for i:=1 to t do writeln(q[i]); 60 while h<t do 61 begin 62 inc(h); 63 x:=q[h];v[x]:=false; 64 i:=head[x]; 65 while i<>0 do 66 begin 67 y:=e[i].go; 68 tmp:=max(d[x],e[i].v2); 69 //writeln(e[i].v1,‘ ‘,xx,‘ ‘,tmp,‘ ‘,d[y]); 70 if (e[i].v1<=xx) and (tmp<d[y]) then 71 begin 72 d[y]:=tmp;//writeln(d[y]); 73 if not(v[y]) then 74 begin 75 v[y]:=true; 76 inc(t);q[t]:=y; 77 end; 78 end; 79 i:=e[i].next; 80 end; 81 end; 82 end; 83 procedure init; 84 begin 85 readln(n,m);mm:=m;m:=0; 86 for i:=1 to n do fa[i]:=i; 87 for i:=1 to mm do 88 begin 89 readln(x,y,z,w); 90 xx:=find(x);yy:=find(y); 91 if xx<>yy then fa[xx]:=yy; 92 if x=y then continue; 93 inc(m);c1[m]:=x;c2[m]:=y;a[m]:=z;b[m]:=w; 94 insert(x,y,z,w);insert(y,x,z,w); 95 end; 96 sort(1,m); 97 // for i:=1 to m do writeln(c1[i],‘ ‘,c2[i],‘ ‘,a[i],‘ ‘,b[i]); 98 end; 99 procedure main;100 begin101 d[1]:=0;102 for i:=2 to n do d[i]:=inf;103 //for i:=1 to n do writeln(i,‘ ‘,d[i],‘ ‘,head[i]);104 l:=1;r:=m;105 while true do106 begin107 fillchar(v,sizeof(v),false);108 while a[l]=a[l+1] do109 begin110 v[c1[l]]:=true;v[c2[l]]:=true;111 inc(l);112 end;113 v[c1[l]]:=true;v[c2[l]]:=true;114 xx:=a[l]; //writeln(xx);115 if l>r then break;116 spfa;117 //for i:=1 to n do writeln(i,‘ ‘,d[i]);118 //if d[n]+xx=19923 then writeln(c1[l],‘ ‘,c2[l],‘ ‘,a[l],‘ ‘,b[l]);119 //writeln(d[n],‘ ‘,xx);120 ans:=min(ans,d[n]+xx);// writeln(d[n],‘ ‘,l,‘ ‘,r,‘ ‘,xx);121 while ans<=a[r] do dec(r);122 inc(l);123 end;124 writeln(ans);125 end;126 begin127 assign(input,‘forest.in‘);assign(output,‘forest.out‘);128 reset(input);rewrite(output);129 init;130 ans:=inf<<1;131 if find(1)<>find(n) then writeln(‘-1‘) else main;132 close(input);close(output);133 end.
5.SPFA再优化75分。。。
1 const inf=maxlongint>>2;maxn=100000+10; 2 type node=record 3 from,go,next,v1,v2:longint; 4 end; 5 var a,b,d,c1,c2,head,fa:array[0..maxn] of longint; 6 q:array[0..10*maxn] of longint; 7 e:array[0..maxn*2] of node; 8 v:array[0..maxn] of boolean; 9 i,j,xx,yy,l,z,w,tot,r,x,y:longint; 10 ans,n,m,mm:int64; 11 function find(x:longint):longint; 12 begin 13 if fa[x]<>x then fa[x]:=find(fa[x]); 14 exit(fa[x]); 15 end; 16 function max(x,y:longint):longint; 17 begin 18 if x>y then exit(x) else exit(y); 19 end; 20 function min(x,y:longint):longint; 21 begin 22 if x<y then exit(x) else exit(y); 23 end; 24 procedure swap(var x,y:longint); 25 var t:longint; 26 begin 27 t:=x;x:=y;y:=t; 28 end; 29 30 procedure sort(l,r:longint); 31 var i,j,x:longint; 32 begin 33 i:=l;j:=r;x:=a[(i+j)>>1]; 34 repeat 35 while a[i]<x do inc(i); 36 while a[j]>x do dec(j); 37 if i<=j then 38 begin 39 swap(a[i],a[j]);swap(b[i],b[j]);swap(c1[i],c1[j]);swap(c2[i],c2[j]); 40 inc(i);dec(j); 41 end; 42 until i>j; 43 if i<r then sort(i,r); 44 if j>l then sort(l,j); 45 end; 46 procedure insert(x,y,z,w:longint); 47 begin 48 inc(tot); 49 with e[tot] do 50 begin 51 from:=x;go:=y;next:=head[x];head[x]:=tot;v1:=z;v2:=w; 52 end; 53 end; 54 procedure spfa; 55 var i,x,y,h,t,tmp:longint; 56 begin 57 h:=0;t:=0; 58 for i:=1 to n do if v[i] then begin inc(t);q[t]:=i;end; 59 //for i:=1 to t do writeln(q[i]); 60 while h<t do 61 begin 62 inc(h); 63 x:=q[h];v[x]:=false; 64 i:=head[x]; 65 while i<>0 do 66 begin 67 y:=e[i].go; 68 tmp:=max(d[x],e[i].v2); 69 //writeln(e[i].v1,‘ ‘,xx,‘ ‘,tmp,‘ ‘,d[y]); 70 if (e[i].v1<=xx) and (tmp<d[y]) then 71 begin 72 d[y]:=tmp;//writeln(d[y]); 73 if not(v[y]) then 74 begin 75 v[y]:=true; 76 inc(t);q[t]:=y; 77 end; 78 end; 79 i:=e[i].next; 80 end; 81 end; 82 end; 83 procedure init; 84 begin 85 readln(n,m);mm:=m;m:=0; 86 for i:=1 to n do fa[i]:=i; 87 for i:=1 to mm do 88 begin 89 readln(x,y,z,w); 90 xx:=find(x);yy:=find(y); 91 if xx<>yy then fa[xx]:=yy; 92 //if x=y then continue; 93 inc(m);c1[m]:=x;c2[m]:=y;a[m]:=z;b[m]:=w; 94 insert(x,y,z,w);insert(y,x,z,w); 95 end; 96 sort(1,m); 97 // for i:=1 to m do writeln(c1[i],‘ ‘,c2[i],‘ ‘,a[i],‘ ‘,b[i]); 98 end; 99 procedure main;100 begin101 d[1]:=0;102 for i:=2 to n do d[i]:=inf;103 //for i:=1 to n do writeln(i,‘ ‘,d[i],‘ ‘,head[i]);104 l:=1;r:=m;105 for i:=1 to n do fa[i]:=i;106 while find(1)<>find(n) do begin fa[find(c1[l])]:=find(c2[l]);inc(l);end;107 //writeln(l,‘ ‘,find(1),‘ ‘,find(n));108 while a[l]=a[l-1] do inc(l);109 v[1]:=true;xx:=a[l-1];spfa;ans:=min(ans,d[n]+xx);110 while true do111 begin112 fillchar(v,sizeof(v),false);113 while a[l]=a[l+1] do114 begin115 v[c1[l]]:=true;v[c2[l]]:=true;116 inc(l);117 end;118 v[c1[l]]:=true;v[c2[l]]:=true;119 xx:=a[l]; //writeln(xx);120 if l>r then break;121 spfa;122 //for i:=1 to n do writeln(i,‘ ‘,d[i]);123 //if d[n]+xx=19923 then writeln(c1[l],‘ ‘,c2[l],‘ ‘,a[l],‘ ‘,b[l]);124 //writeln(d[n],‘ ‘,xx);125 ans:=min(ans,d[n]+xx);// writeln(d[n],‘ ‘,l,‘ ‘,r,‘ ‘,xx);126 while ans<=a[r] do dec(r);127 inc(l);128 end;129 writeln(ans);130 end;131 begin132 assign(input,‘forest.in‘);assign(output,‘forest.out‘);133 reset(input);rewrite(output);134 init;135 ans:=inf<<1;136 if find(1)<>find(n) then writeln(‘-1‘) else main;137 close(input);close(output);138 end.
6.原来发现数组开小了。。。100分，苦逼的调试
1 const inf=maxlongint>>2;maxn=100000+10; 2 type node=record 3 from,go,next,v1,v2:longint; 4 end; 5 var a,b,d,c1,c2,head,fa:array[0..maxn] of longint; 6 q:array[0..100*maxn] of longint; 7 e:array[0..maxn*2] of node; 8 v:array[0..maxn] of boolean; 9 i,j,xx,yy,l,z,w,tot,r,x,y:longint; 10 ans,n,m,mm:int64; 11 function find(x:longint):longint; 12 begin 13 if fa[x]<>x then fa[x]:=find(fa[x]); 14 exit(fa[x]); 15 end; 16 function max(x,y:longint):longint; 17 begin 18 if x>y then exit(x) else exit(y); 19 end; 20 function min(x,y:longint):longint; 21 begin 22 if x<y then exit(x) else exit(y); 23 end; 24 procedure swap(var x,y:longint); 25 var t:longint; 26 begin 27 t:=x;x:=y;y:=t; 28 end; 29 30 procedure sort(l,r:longint); 31 var i,j,x:longint; 32 begin 33 i:=l;j:=r;x:=a[(i+j)>>1]; 34 repeat 35 while a[i]<x do inc(i); 36 while a[j]>x do dec(j); 37 if i<=j then 38 begin 39 swap(a[i],a[j]);swap(b[i],b[j]);swap(c1[i],c1[j]);swap(c2[i],c2[j]); 40 inc(i);dec(j); 41 end; 42 until i>j; 43 if i<r then sort(i,r); 44 if j>l then sort(l,j); 45 end; 46 procedure insert(x,y,z,w:longint); 47 begin 48 inc(tot); 49 with e[tot] do 50 begin 51 from:=x;go:=y;next:=head[x];head[x]:=tot;v1:=z;v2:=w; 52 end; 53 end; 54 procedure spfa; 55 var i,x,y,h,t,tmp:longint; 56 begin 57 //writeln(1); 58 h:=0;t:=0; 59 for i:=1 to n do if v[i] then begin inc(t);q[t]:=i;end; 60 //for i:=1 to t do writeln(q[i]); 61 while h<t do 62 begin 63 inc(h); 64 x:=q[h];v[x]:=false; //writeln(x); 65 i:=head[x]; 66 while i<>0 do 67 begin 68 y:=e[i].go; 69 tmp:=max(d[x],e[i].v2); 70 //writeln(e[i].v1,‘ ‘,xx,‘ ‘,tmp,‘ ‘,d[y]); 71 if (e[i].v1<=xx) and (tmp<d[y]) then 72 begin 73 d[y]:=tmp;//writeln(d[y]); 74 if not(v[y]) then 75 begin 76 v[y]:=true; 77 inc(t);q[t]:=y; 78 end; 79 end; 80 i:=e[i].next; 81 end; 82 end; 83 end; 84 procedure init; 85 begin 86 readln(n,m);mm:=m;m:=0; 87 for i:=1 to n do fa[i]:=i; 88 for i:=1 to mm do 89 begin 90 readln(x,y,z,w); 91 xx:=find(x);yy:=find(y); 92 if xx<>yy then fa[xx]:=yy; 93 if x=y then continue; 94 inc(m);c1[m]:=x;c2[m]:=y;a[m]:=z;b[m]:=w; 95 insert(x,y,z,w);insert(y,x,z,w); 96 end; 97 sort(1,m);//writeln(m); 98 //for i:=1 to m do writeln(i,‘ ‘,c1[i],‘ ‘,c2[i],‘ ‘,a[i],‘ ‘,b[i]); 99 end;100 procedure main;101 begin102 d[1]:=0;103 for i:=2 to n do d[i]:=inf;104 //for i:=1 to n do writeln(i,‘ ‘,d[i],‘ ‘,head[i]);105 l:=1;r:=m;106 for i:=1 to n do fa[i]:=i;107 while find(1)<>find(n) do108 begin109 //writeln(l,‘ ‘,find(1),‘ ‘,find(n));110 //writeln(c1[l],‘ ‘,c2[l]);111 xx:=find(c1[l]);yy:=find(c2[l]);112 if xx<>yy then fa[xx]:=yy;113 inc(l);114 end;115 //writeln(l,‘ ‘,find(1),‘ ‘,find(n));116 while a[l]=a[l-1] do inc(l);//writeln(l);117 v[1]:=true;xx:=a[l-1];//writeln(xx);118 spfa;119 //for i:=1 to n do writeln(i,‘ ‘,d[i]);120 ans:=min(ans,d[n]+xx);//writeln(‘ ‘,ans);121 while true do122 begin123 //writeln(‘ ‘,ans);124 fillchar(v,sizeof(v),false);125 if l>r then break;126 while a[l]=a[l+1] do127 begin128 v[c1[l]]:=true;v[c2[l]]:=true;129 inc(l);130 end;131 v[c1[l]]:=true;v[c2[l]]:=true;132 xx:=a[l]; //writeln(xx);133 if l>r then break;134 spfa;135 //for i:=1 to n do writeln(i,‘ ‘,d[i]);136 //if d[n]+xx=19923 then writeln(c1[l],‘ ‘,c2[l],‘ ‘,a[l],‘ ‘,b[l]);137 //writeln(d[n],‘ ‘,xx);138 ans:=min(ans,d[n]+xx);//writeln(d[n],‘ ‘,l,‘ ‘,r,‘ ‘,xx);139 while ans<=a[r] do dec(r);140 inc(l);141 end;142 writeln(ans);143 end;144 begin145 assign(input,‘forest.in‘);assign(output,‘forest.out‘);146 reset(input);rewrite(output);147 init;148 ans:=inf<<1;149 if find(1)<>find(n) then writeln(‘-1‘) else main;150 close(input);close(output);151 end.
7.去掉调试更清晰。。。
1 const inf=maxlongint>>2;maxn=100000+10; 2 type node=record 3 from,go,next,v1,v2:longint; 4 end; 5 var a,b,d,c1,c2,head,fa:array[0..maxn] of longint; 6 q:array[0..100*maxn] of longint; 7 e:array[0..maxn*2] of node; 8 v:array[0..maxn] of boolean; 9 i,j,xx,yy,l,z,w,tot,r,x,y:longint; 10 ans,n,m,mm:int64; 11 function find(x:longint):longint; 12 begin 13 if fa[x]<>x then fa[x]:=find(fa[x]); 14 exit(fa[x]); 15 end; 16 function max(x,y:longint):longint; 17 begin 18 if x>y then exit(x) else exit(y); 19 end; 20 function min(x,y:longint):longint; 21 begin 22 if x<y then exit(x) else exit(y); 23 end; 24 procedure swap(var x,y:longint); 25 var t:longint; 26 begin 27 t:=x;x:=y;y:=t; 28 end; 29 30 procedure sort(l,r:longint); 31 var i,j,x:longint; 32 begin 33 i:=l;j:=r;x:=a[(i+j)>>1]; 34 repeat 35 while a[i]<x do inc(i); 36 while a[j]>x do dec(j); 37 if i<=j then 38 begin 39 swap(a[i],a[j]);swap(b[i],b[j]);swap(c1[i],c1[j]);swap(c2[i],c2[j]); 40 inc(i);dec(j); 41 end; 42 until i>j; 43 if i<r then sort(i,r); 44 if j>l then sort(l,j); 45 end; 46 procedure insert(x,y,z,w:longint); 47 begin 48 inc(tot); 49 with e[tot] do 50 begin 51 from:=x;go:=y;next:=head[x];head[x]:=tot;v1:=z;v2:=w; 52 end; 53 end; 54 procedure spfa; 55 var i,x,y,h,t,tmp:longint; 56 begin 57 h:=0;t:=0; 58 for i:=1 to n do if v[i] then begin inc(t);q[t]:=i;end; 59 while h<t do 60 begin 61 inc(h); 62 x:=q[h];v[x]:=false; 63 i:=head[x]; 64 while i<>0 do 65 begin 66 y:=e[i].go; 67 tmp:=max(d[x],e[i].v2); 68 if (e[i].v1<=xx) and (tmp<d[y]) then 69 begin 70 d[y]:=tmp; 71 if not(v[y]) then 72 begin 73 v[y]:=true; 74 inc(t);q[t]:=y; 75 end; 76 end; 77 i:=e[i].next; 78 end; 79 end; 80 end; 81 procedure init; 82 begin 83 readln(n,m);mm:=m;m:=0; 84 for i:=1 to n do fa[i]:=i; 85 for i:=1 to mm do 86 begin 87 readln(x,y,z,w); 88 xx:=find(x);yy:=find(y); 89 if xx<>yy then fa[xx]:=yy; 90 if x=y then continue; 91 inc(m);c1[m]:=x;c2[m]:=y;a[m]:=z;b[m]:=w; 92 insert(x,y,z,w);insert(y,x,z,w); 93 end; 94 sort(1,m); 95 96 end; 97 procedure main; 98 begin 99 d[1]:=0;100 for i:=2 to n do d[i]:=inf;101 l:=1;r:=m;102 for i:=1 to n do fa[i]:=i;103 while find(1)<>find(n) do104 begin105 xx:=find(c1[l]);yy:=find(c2[l]);106 if xx<>yy then fa[xx]:=yy;107 inc(l);108 end;109 while a[l]=a[l-1] do inc(l);110 v[1]:=true;xx:=a[l-1];111 spfa;112 ans:=min(ans,d[n]+xx);113 while true do114 begin115 fillchar(v,sizeof(v),false);116 if l>r then break;117 while a[l]=a[l+1] do118 begin119 v[c1[l]]:=true;v[c2[l]]:=true;120 inc(l);121 end;122 v[c1[l]]:=true;v[c2[l]]:=true;123 xx:=a[l];124 if l>r then break;125 spfa;126 ans:=min(ans,d[n]+xx);127 while ans<=a[r] do dec(r);128 inc(l);129 end;130 writeln(ans);131 end;132 begin133 assign(input,‘forest.in‘);assign(output,‘forest.out‘);134 reset(input);rewrite(output);135 init;136 ans:=inf<<1;137 if find(1)<>find(n) then writeln(‘-1‘) else main;138 close(input);close(output);139 end.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。