裸的最短路树应用，只用考虑修改最短路树上面的边，其它的边对最短路没有影响。（如果能找出最短路链，应该能更加的优化，但是我就没管了，反正数据比较小）
#include<bits/stdc++.h>
inline void read(int&a)
{
a=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=(a<<1)+(a<<3)+c-'0';
c=getchar();
}
}
inline void write(int a)
{
if(a<0){putchar('-');a=-a;}
if(a>9)write(a/10);
putchar(a%10+'0');
}
#define smaxn 200001
#define pmaxn 1001
int n,m,d=-1;
int point[pmaxn],on_chain[pmaxn],next[smaxn],to[smaxn],len[smaxn];
double p[smaxn];
double ans=0.0;
inline void add(int a,int b,int c,double e)
{
next[++d]=point[a];
to[d]=b;
len[d]=c;
point[a]=d;
p[d]=e;
}
int prior[pmaxn],dis[pmaxn];
int que[500000],start,end;
bool in_que[pmaxn],exist[smaxn];
inline int spfa()
{
start=0;end=-1;
memset(in_que,false,sizeof(in_que));
memset(dis,0x7f,sizeof(dis));
dis[1]=0;in_que[1]=true;que[++end]=1;
while(end>=start)
{
int p=que[start],side=point[p];
while(side!=-1)
{
if(exist[side]&&(dis[to[side]]>dis[p]+len[side]))
{
prior[to[side]]=side;
dis[to[side]]=dis[p]+len[side];
if(!in_que[to[side]])
{
que[++end]=to[side];
in_que[to[side]]=true;
}
}
side=next[side];
}
in_que[p]=false;
++start;
}
if(dis[n]<dis[0])return dis[n];
else return 0;
}
int main()
{
memset(point,-1,sizeof(point));
read(n);read(m);
int u,v,l;
double pi;
for(int i=1;i<=m;i++)
{
read(u);read(v);read(l);scanf("%lf",&pi);
add(u,v,l,pi);add(v,u,l,pi);
}
memset(on_chain,-1,sizeof(on_chain));
memset(exist,true,sizeof(exist));
int k=spfa(),q=0;
double del=0;
for(int i=2;i<=n;i++){del+=p[prior[i]];on_chain[++q]=prior[i];}
ans+=(double)(k)*(1-del);
for(int i=1;i<=q;i++)
{
if(p[on_chain[i]]>0&&on_chain[i]>-1)
{
exist[on_chain[i]]=false;exist[on_chain[i]^1]=false;
ans+=(double)(spfa())*p[on_chain[i]];
exist[on_chain[i]]=true;exist[on_chain[i]^1]=true;
}
}
printf("%.7lf",ans);
return 0;
}