新手刚入门图论，模板是书上的QWQ

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

struct Node {
    int v;
    double dis;
    Node(int _v, double _dis) : v(_v), dis(_dis) {}
};

vector<Node> Adj[2010];

int n, num[2010];
bool inq[2010];

double d[2010];

bool SPFA(int s) {
    memset(inq, false, sizeof(inq));
    memset(num, 0, sizeof(num));
    fill(d, d + 2010, 0);

    queue<int> Q;
    Q.push(s);
    inq[s] = true;
    num[s]++;
    d[s] = 1;

    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        inq[u] = false;
        for (int j = 0; j < Adj[u].size(); j++) {
            int v = Adj[u][j].v;
            double dis = Adj[u][j].dis;
            if (d[v] < d[u] * dis) {
                d[v] = d[u] *  dis;
                if (!inq[v]) {
                    Q.push(v);
                    inq[v] = true;
                    num[v]++;
                    if (num[v] >= n) return false;
                }
            }
        }
    }

    return true;
}

int main() {
    int m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        Adj[x].push_back(Node(y, 1 - (double)z / 100.0));
    }
    int A, B;
    scanf("%d %d", &A, &B);
    SPFA(A);
    printf("%.8lf", 100.0 / d[B]);

    return 0;
}