洛谷P1576 最小花费 最短路变形题

题目链接：https://www.luogu.com.cn/problem/P1576

解题思路完全参照自 zjy111 大神的博客：https://www.luogu.com.cn/blog/zjy111/solution-p1576

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2020, maxm = 200020;
struct Edge {
    int v, nxt;
    double w;
    Edge() {};
    Edge(int _v, double _w, int _nxt) { v = _v; w = _w; nxt = _nxt; }
} edge[maxm];
int n, m, head[maxn], ecnt;
void init() {
    ecnt = 0;
    memset(head, -1, sizeof(int)*(n+1));
}
void addedge(int u, int v, double w) {
    edge[ecnt] = Edge(v, w, head[u]); head[u] = ecnt ++;
    edge[ecnt] = Edge(u, w, head[v]); head[v] = ecnt ++;
}
struct Node {
    int u;
    double dis;
    Node() {};
    Node(int _u, double _dis) { u = _u; dis = _dis; }
    bool operator < (const Node& x) const {
        return dis < x.dis;
    }
};
priority_queue<Node> que;
double dis[maxn];
bool vis[maxn];
void dijkstra(int s) {
    for (int i = 1; i <= n; i ++) dis[i] = 0;
    dis[s] = 1;
    que.push(Node(s, 1));
    while (!que.empty()) {
        Node nd = que.top();
        que.pop();
        int u = nd.u;
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edge[i].nxt) {
            int v = edge[i].v;
            double w = edge[i].w;
            if (!vis[v] && dis[v] < dis[u] * w) {
                dis[v] = dis[u] * w;
                que.push(Node(v, dis[v]));
            }
        }
    }
}
int main() {
    cin >> n >> m;
    init();
    while (m --) {
        int u, v;
        double w;
        cin >> u >> v >> w;
        addedge(u, v, (100.0 - w) / 100.0);
    }
    int a, b;
    cin >> a >> b;
    dijkstra(a);
    printf("%.8lf
", 100.0 / dis[b]);
    return 0;
}