题意：
此题中S=1
思路：Orz ManGod秒切此题
我觉得出入边权互换不太直观，就改了一下写法
第一次默认与1有关的第一条出边只出不入，第二次默认只入不出
1 var q,dis:array[1..150000]of longint; 2 head,vet,next,len,flag,x,y,z,w,id,a,b,c,d:array[1..300000]of longint; 3 inq:array[1..50000]of boolean; 4 n,m,bz,t3,t4,tot,h1,t1,i,j,ans,m1,t,tmp:longint; 5 6 procedure add(a,b,c:longint); 7 begin 8 inc(tot); 9 next[tot]:=head[a]; 10 vet[tot]:=b; 11 len[tot]:=c; 12 head[a]:=tot; 13 end; 14 15 function who(x,y:longint):longint; 16 begin 17 if x=1 then exit(y); 18 exit(x); 19 end; 20 21 function min(x,y:longint):longint; 22 begin 23 if x<y then exit(x); 24 exit(y); 25 end; 26 27 procedure spfa; 28 var u,e,v,t,w:longint; 29 begin 30 t:=0; w:=t1; 31 while h1<t1 do 32 begin 33 inc(h1); inc(t); 34 if t=3*n+1 then t:=1; 35 u:=q[t]; inq[u]:=false; 36 e:=head[u]; 37 while e<>0 do 38 begin 39 v:=vet[e]; 40 if (flag[e]=0)and(dis[u]+len[e]<dis[v]) then 41 begin 42 dis[v]:=dis[u]+len[e]; 43 if not inq[v] then 44 begin 45 inc(t1); inc(w); 46 if w=3*n+1 then w:=1; 47 q[w]:=v; inq[v]:=true; 48 end; 49 end; 50 e:=next[e]; 51 end; 52 end; 53 end; 54 55 procedure swap(var x,y:longint); 56 var t:longint; 57 begin 58 t:=x; x:=y; y:=t; 59 end; 60 61 begin 62 assign(input,'bzoj4398.in'); reset(input); 63 assign(output,'bzoj4398.out'); rewrite(output); 64 readln(n,m1); 65 for i:=1 to m1 do 66 begin 67 read(x[i],y[i],z[i],w[i]); 68 if (x[i]=1)or(y[i]=1) then 69 begin 70 inc(m); id[m]:=i; 71 a[m]:=x[i]; b[m]:=y[i]; c[m]:=z[i]; d[m]:=w[i]; 72 end; 73 add(x[i],y[i],z[i]); 74 add(y[i],x[i],w[i]); 75 end; 76 77 t:=trunc(ln(n)/ln(2))+1; 78 ans:=maxlongint; 79 for i:=1 to t do 80 begin 81 for j:=1 to tot do flag[j]:=0; 82 bz:=who(a[1],b[1]); 83 if a[1]=1 then flag[id[1]<<1]:=1 84 else flag[(id[1]<<1)-1]:=1; //out 85 86 fillchar(inq,sizeof(inq),false); 87 fillchar(dis,sizeof(dis),$7f); 88 h1:=0; t1:=0; 89 inc(t1); q[t1]:=bz; inq[bz]:=true; 90 if a[1]=1 then dis[bz]:=c[1] 91 else dis[bz]:=d[1]; 92 93 for j:=2 to m do 94 begin 95 tmp:=who(a[j],b[j]); 96 t3:=bz and (1<<(i-1)); 97 t4:=tmp and (1<<(i-1)); 98 if t3<>t4 then //in 99 begin 100 if a[j]=1 then flag[(id[j]<<1)-1]:=1 101 else flag[id[j]<<1]:=1; 102 end 103 else //out 104 begin 105 if a[j]=1 then flag[id[j]<<1]:=1 106 else flag[(id[j]<<1)-1]:=1; 107 inc(t1); q[t1]:=tmp; inq[tmp]:=true; 108 if a[j]=1 then dis[tmp]:=c[j] 109 else dis[tmp]:=d[j]; 110 end; 111 end; 112 spfa; 113 ans:=min(ans,dis[1]); 114 end; 115 116 117 for i:=1 to t do 118 begin 119 for j:=1 to tot do flag[j]:=0; 120 bz:=who(a[1],b[1]); 121 if a[1]=1 then flag[(id[1]<<1)-1]:=1 122 else flag[id[1]<<1]:=1; //in 123 124 fillchar(inq,sizeof(inq),false); 125 fillchar(dis,sizeof(dis),$7f); 126 h1:=0; t1:=0; 127 128 129 for j:=2 to m do 130 begin 131 tmp:=who(a[j],b[j]); 132 t3:=bz and (1<<(i-1)); 133 t4:=tmp and (1<<(i-1)); 134 if t3<>t4 then //out 135 begin 136 if a[j]=1 then flag[id[j]<<1]:=1 137 else flag[(id[j]<<1)-1]:=1; 138 inc(t1); q[t1]:=tmp; inq[tmp]:=true; 139 if a[j]=1 then dis[tmp]:=c[j] 140 else dis[tmp]:=d[j]; 141 end 142 else //in 143 begin 144 if a[j]=1 then flag[(id[j]<<1)-1]:=1 145 else flag[id[j]<<1]:=1; 146 end; 147 end; 148 spfa; 149 ans:=min(ans,dis[1]); 150 end; 151 if ans>1000000000 then writeln(-1) 152 else writeln(ans); 153 close(input); 154 close(output); 155 end.