方法1:
已知某一个人手里的金额为a,以及他转给下一个人时的要扣除的手续费百分比(边权w),假设下一个人实际拿到的金额为b,则有 $ a - a * w = b$,也即: $ a * (1 - w) = b$。
反过来说,如果已经知道最后b能够拿到的钱,就能推出a当时有多少钱: $b / (1 - w) = a$
因此,在读取边权时,处理一下,可以认为边权w = (100 - w) / 100(剩余的金额的百分比)。
然后从终点(100元)出发,反着推一开始最少有多少钱。
#include <iostream>
using namespace std;
#include <cstring>
#include <algorithm>
#include <queue>
const static int N = 2010, M = 1e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[M], nex[M], idx;
double w[M];
double dist[N];
bool st[N];
int n, m;
int a, b;
using PDI = pair<double, int>;
priority_queue<PDI, vector<PDI>, greater<PDI>> heap;
void add(int a, int b, double c)
{
w[idx] = c, e[idx] = b, nex[idx] = h[a], h[a] = idx++;
}
void dijkstra()
{
memset(dist, 0x43, sizeof dist);
dist[b] = 100.0;
heap.push({ dist[b], b });
while (heap.size())
{
PDI t = heap.top();
heap.pop();
int ver = t.second;
double distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = nex[i])
{
int j = e[i];
if (dist[j] > distance / w[i])
{
dist[j] = distance / w[i];
heap.push({ dist[j], j });
}
}
}
}
// 从B走到A的最短路径
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; ++i)
{
int a, b;
double c;
cin >> a >> b >> c;
c = (1.0 - c / 100);
add(a, b, c), add(b, a, c);
}
cin >> a >> b;
dijkstra();
printf("%.8lf", dist[a]);
}
方法二:
与方法一思想类似,只不过在计算过程中不考虑金额,只考虑百分比系数
若输入百分比系数w,令 $w = (100 - w) / 100$, 初始金额, 最后的金额b
$b = a * w_1 * w_2 * w_3$,要使a最小,则w需最大。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <algorithm>
#include <cstring>
const static int N = 2010;
double rect[N][N];
bool st[N];
double d[N];
int n, m;
int a, b;
double dijkstra()
{
d[a] = 1;
for (int i = 0; i < n - 1; ++i)
{
int t = -1;
for (int j = 1; j <= n; ++j)
if (!st[j] && (t == -1 || d[t] < d[j]))
t = j;
st[t] = true;
for (int i = 1; i <= n; ++i)
{
d[i] = max(d[i], d[t] * rect[t][i]);
}
}
return d[b];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; ++i)
{
int a, b, c;
cin >> a >> b >> c;
double z = (100.0 - c) / 100;
if (a != b) rect[a][b] = rect[b][a] = max(rect[a][b], z);
}
cin >> a >> b;
double res = dijkstra();
printf("%.8lf", 100.0 / res);
}
%%%