传送门

class Solution {
public:
    int n,m,s,t; 
    struct node{
        int id;
        double dist;
        node()
        {
            id=0;dist=0;
        }
        node(int c,int d)
        {
            id=c;dist=d;
        }
        bool operator < (const node &x)const
        {
            return x.dist>dist;
        }
    };
    priority_queue<node> que;
    struct linkstar{
        int to,from;
        double w;
        int next;
    }edge[11000];
    int head[11000];
    double dis[11000];
    int vis[11000];
    int escnt;
    void add(int from,int to,double w)
    {
        edge[escnt].from=from;
        edge[escnt].to=to;
        edge[escnt].w=w;
        edge[escnt].next=head[from];
        head[from]=escnt;
        escnt++;
    }
    void Dijkstra(int u)
    {
        dis[u]=1;
        que.push(node(u,1));
        int cnt=0;
        while(que.size())
        {
            node cp=que.top();
            que.pop();
            if(vis[cp.id]) continue;
            cnt++;
            vis[cp.id]=true;
            for (int i=head[cp.id];i!=-1;i=edge[i].next)
            {
                if(dis[edge[i].to]<dis[cp.id]*edge[i].w)
                {
                    dis[edge[i].to]=dis[cp.id]*edge[i].w;
                    //cout<<dis[edge[i].to]<<endl;
                    if(!vis[edge[i].to])
                    {
                        que.push(node(edge[i].to,dis[edge[i].to]));
                    }
                }
            }
        }
    }
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        memset(head,-1,sizeof(head));
        for (int i=0;i<edges.size();i++)
        {
            add(edges[i][0],edges[i][1],succProb[i]);
            add(edges[i][1],edges[i][0],succProb[i]);
        }
        Dijkstra(start);
        return dis[end];
    }
};