题目描述
解题思路
特别之处：由于手续费我们要尽可能取最小值，即(100 - c) / 100 要尽可能大
因此：初始化时使用max而不是min，并且获取未添加到集合中的元素时，也要选择更大的！
包括更新其他边也要取max！
关于乘法：dist[S]*w[1]*w[2]...w[n] = dist[T]
- 两边同时取对数，则左边转变为加法，即可说明加法和乘法其实是一样的，由于w[i]为0-1，所以取了对数是负数！
- 令dist[T]最大！我们可以左右同乘-1，即目标变为令-dist[T]最小，这时就转化为了最短路问题！
- 且左边都变为了正数，这时可以使用dijkstra和spfa任意一种！代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int n, m, S, T;
double dist[N], g[N][N];
bool vis[N];
void dijkstra()
{
dist[S] = 1;
for (int i = 1; i <= n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
if (!vis[j] && (t == -1 || dist[t] < dist[j])) // 注意符号
t = j;
vis[t] = true;
for (int j = 1; j <= n; j++)
dist[j] = max(dist[j], dist[t] * g[t][j]);
}
}
int main()
{
scanf("%d%d", &n, &m);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
double z = (100.0 - c) / 100;
g[a][b] = g[b][a] = max(g[a][b], z);
}
cin >> S >> T;
dijkstra();
printf("%.8lf\n", 100 / dist[T]);
return 0;
}
