边权为1，在维护最短路的同时维护p值最小，我直接存的(1-p)，即不遇见的概率，要使得这个值最大。
#include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define eps 1e-6 #define ll long long const int maxn=100010; const int maxm=100010; using namespace std; struct node { int v,w,next; double p; }e[maxm<<1]; int vis[maxn],h,head[maxn],n,m,d[maxn],pre[maxn]; double p[maxn]; void addedge(int a,int b,double c) { e[h].v=b; e[h].w=1; e[h].p=c; e[h].next=head[a]; head[a]=h++; } void spfa(int s) { int x,v,i; for(i=0;i<=n;i++) p[i]=0,d[i]=inf; memset(vis,0,sizeof vis); memset(pre,-1,sizeof pre); p[s]=1,vis[s]=1,d[s]=0; queue q; q.push(s); while(!q.empty()) { x=q.front(); q.pop(); vis[x]=0; for(i=head[x];i!=-1;i=e[i].next) { v=e[i].v; if(d[v]>d[x]+1) { d[v]=d[x]+1; p[v]=p[x]*e[i].p; pre[v]=x; if(!vis[v]) { vis[v]=1; q.push(v); } } else if(d[v]==d[x]+1) { if(p[v]