罗嘉为 • 11个月前
评论:
using namespace std;
double a[2100][2100], dis[2100] = {0}, maxn; int n, m, i, j, k, x, y, f[2100] = {0};
void init(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> j >> k;
cin >> a[j][k];
a[j][k] = (100 - a[j][k]) / 100;
a[k][j] = a[j][k];
}
cin >> x >> y;
} void di(int x){
for(int i = 1; i <= n; i++){
dis[i] = a[x][i];
}
dis[x] = 1; f[x] = 1;
for(int i = 1; i <= n - 1; i++){
maxn = 0;
for(int j = 1; j <= n; j++){
if(f[j] == 0 && dis[j] > maxn){
k = j;
maxn = dis[j];
}
}
f[k] = 1;
if(k == y) break;
for(int j = 1; j <= n; j++){
if(f[j] == 0 && dis[k] * a[k][j] > dis[j]){
dis[j] = dis[k] * a[k][j];
}
}
}
}
int main(){
init();
di(x);
printf("%0.8lf", 100 / dis[y]);
return 0;
}