SPFA 算法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue> 
#include <unordered_set>

using namespace std;
const int MAXN = 2000+10;
//int a[MAXN];
struct Item {
    int v;
    double w;
};
int n,m;
int A,B;
unordered_map<int,vector<Item>> path;
double dist[MAXN];

double spfa() {
    //memset(dist,1,sizeof dist);
    queue<int> q;
    unordered_set<int> inq;
    dist[A] = 1;
    q.push(A);
    inq.insert(A);
    while(q.size()) {
        int  u  = q.front();q.pop();
        inq.erase(u);
        for(auto &temp: path[u]) {
            int v = temp.v;
            double d = temp.w;
            if(dist[v] <= dist[u] *d /100 ) {
                dist[v] = dist[u] *d /100;
                if(inq.count(v) ==0) {
                    inq.insert(v);
                    q.push(v);

                }
            }
        }
    }
    return dist[B];
}



int main()
{
    cin>>n >>m;
    while(m--) {
        int x,y,d;
        cin>> x>>y >>d;
        path[x].push_back({y, (100 - d) });
        path[y].push_back({x,(100 - d)});

    }


    cin>> A>>B;

    //数据保证 A 与 B 之间可以直接或间接地转账。
   // cout << 100/ spfa() <<endl;
    printf("%.8lf",100/spfa());

    return 0;
}