#include <bits/stdc++.h> using namespace std; double a[2100][2100], dis[2100] = {0}, maxn; int n, m, i, j, k, x, y, f[2100] =

罗嘉为  •  11个月前



评论:

include <bits/stdc++.h>

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;

}


罗嘉为  •  11个月前