$$\color{Red}{最小花费——【乘积边权抽象成最短路(证明推导)】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

解析

这道题难点不在于选什么算法，其实这道题数据量 n <= 100，选最坏的代码最少的多源最短路 floyd ，也只需要最坏的情况下为 1 * 10 ^ 6，可以在 1秒内ac。

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，代码中的操作次数控制在 10 ^ 7 ∼ 10 ^ 8 为最佳。

n <= 100 -> O(n ^ 3) -> 状态压缩dp floyd 高斯消元

n <= 1000 -> O(n ^ 2) O(n ^ 2 * log(n)) -> dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford

n ≤ 100000 -> O(nlogn) -> 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa

思路

这道题第一直觉，首先肯定是要建图，想到可以用搜索做，即bfs，进一步思考bfs的优化就到了spfa，但是这道题y总给了一个证明，也让我们理解为什么可以把乘积边权的情况，化为最短路问题。

这道题首先我们把每个人抽象成一个节点，应该是无向图，两个人之间可以转账，为了让计算变得简洁，我们肯定把边权直接看作 (100.0 - c) / 100.0更容易计算。【题目说了，给的数据是手续费 c %】，我们这里用g[a][b]代表两个人之间转账的剩余率。

那么我们假设起点即A节点是S,终点即B节点是T,显然他们两个转账可以经过各种各样的路径。

而最终转账的钱即 money * w[1] * w[2] * ..... * w[n]，这里其中的参数代表经过转账的每个人彼此的剩余率。

那么钱是固定的情况下，我们把后面的整体取对数。

即 logw1 + logw2 + .... + logwn

而我们知道这个w的取值范围，因为手续费的利率，在[0, 1)，故 w -> (0, 1]，而对数函数，单调递增，且log(0) == 0.

故每个 logw 均小于0,即求负的 logw1 + logw2 + .... + logwn 的最大值，等同于求正数之和的最小值。

且知道 log(w) < 0，故取反衡为正权边，故证明这道题是可以使用 dijkstra的。

以上可以引申出以下结论

乘积的最短路问题

当 w >= 1的情况下，天然满足求最短路的情况，即求正的 logw1 + logw2 + .... + logwn 的最小值，且已知每一项均严格大于等于0. 可使用dijkstra

当 w -> (0, 1]，即为本题情况，也可使用dijkstra

而若 w >= 0 , 此时 logw1 + logw2 + .... + logwn 的各项可正可负，故不满足均为正权或负权【负权求最远等价正权求最短路】,此时只能使用spfa

我的SPFA全题解

我的Dijkstra全题解

我的Bellman_fold全题解

我的Floyd全题解

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


/**
 * @author Fanxy
 */
public class Main {

    static int n, m, S, T, N = 2010;
    static double[][] g = new double[N][N];
    static double[] d = new double[N];
    static boolean[] st = new boolean[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void dijkstra() {
        d[S] = 1;
        for (int i = 1; i <= n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++)
                if (!st[j] && (t == -1 || d[j] > d[t]))
                    t = j;
            st[t] = true;
            for (int j = 1; j <= n; j++) {
                d[j] = Math.max(d[j], d[t] * g[t][j]);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 0; i < m; i++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            g[a][b] = g[b][a] = Math.max(g[a][b], (100.0 - c) / 100.0);
        }
        String [] s3 = br.readLine().split(" ");
        S = Integer.parseInt(s3[0]);
        T = Integer.parseInt(s3[1]);
        dijkstra();
        System.out.printf("%.8f", 100 / d[T]);
    }
}