设刚开始的钱是x,每两个人之间的交易率
则$100=x * (w_{1} * w_{2} * w_{3}..)$
要想$x$最小,就要求$w_{1} * w_{2} * w_{3}..$最大
即求$log(w_1 * w_2 * w_3..) = log(w_1) + log(w_2) + .. $最大,
因为$w$都是小于$1$的,所以$log(w)$都是小于$0$的,所以将每个数取相反数,
问题转化成求取反后的最小值,即转换成最短路问题
C++ 代码
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 2010 , M = 200010;
int e[M] , ne[M] , h[N] , idx;
double d[M] , w[M];
bool st[N];
int n , m;
void add(int a , int b , double c)
{
e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx++;
}
double spfa(int a , int b)
{
queue<int> q;
q.push(a);
d[a] = 1;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t] ; ~i ; i = ne[i])
{
int j = e[i];
if(d[j] < d[t] * (1 - w[i]))
{
d[j] = d[t] * (1 - w[i]);
if(!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
return d[b];
}
int main()
{
cin >> n >> m;
memset(h , -1 , sizeof h);
while(m--)
{
int a , b , c;
cin >> a >> b >> c;
add(a , b , 1.0 * c / 100) , add(b , a , 1.0 * c / 100);
}
int a , b;
cin >> a >> b;
printf("%.8lf\n" , 100 / spfa(a , b));
return 0;
}
spfa函数里对d数组的memset应该是诈胡了吧?想求最大值结果初始化成了正无穷,但是刚好d是double,结果用0x3f初始化成了一个很小的数?
啊对 多谢指正
看懂转换关系了,但是大佬您的做法中也没有“求取反后的最小值”,没有取反这个操作啊
好像二者没啥关系吧
思路解释很简洁