0分求调
查看原帖
0分求调
1126670
cysxc11111楼主2024/1/13 15:34
#include<bits/stdc++.h>
using namespace std;
double e[2001][2001],dis[2001]={0},minn;
int main(){
	int n,m,x,y,z,a,b,u;
	double inf=99999999;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) e[i][j]=1;
			else e[i][j]=inf;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		e[x][y]=e[y][x]=1-(double)z/100;
	}
	cin>>a>>b;
	int book[2001]={0};
	book[a]=1;
	for(int i=1;i<=n;i++) dis[i]=e[a][i];
	for(int i=1;i<=n-1;i++){
		minn=0;
		for(int j=1;j<=n;j++){
			if(book[j]==0&&dis[j]>minn){
				minn=dis[j];
				u=j;
			}
		}
		book[u]=1;
		for(int v=1;v<=n;v++){
			if(e[u][v]<inf){
				if(book[v]==0&&dis[v]<dis[u]*e[u][v])
					dis[v]=dis[u]*e[u][v];
			}
		}
	}
	cout<<fixed<<setprecision(8)<<100/dis[b]<<endl;
	return 0;
}
2024/1/13 15:34
加载中...