样例和测试一都过了,0pts求调
查看原帖
样例和测试一都过了,0pts求调
730717
wanwang楼主2023/8/9 15:25
#include<bits/stdc++.h>
#define MAXN 2005
using namespace std;
namespace IO{
	char ibuf[(1<<20)+1],*iS,*iT;
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	inline long long read(){
		char ch=gh();
		long long x=0;
		bool t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline char getc(){
		char ch=gh();
		while(ch<'a'||ch>'z') ch=gh();
		return ch;
	}
}
using IO::read;//可获取标准输入中下一个未被读入的 64 位有符号整数。
using IO::getc;//可获取标准输入中下一个未被读入的小写字母。
int n,m,x,y,k;
bool f[MAXN];
double a[MAXN][MAXN],dis[MAXN];
void input(){
	n=read();
	m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		scanf("%lf",&a[u][v]);
		a[u][v]=(100-a[u][v])/100;
		a[v][u]=a[u][v];
	}
	x=read();
	y=read();
}
void dj(){
	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++){
		double maxn=0;
		for(int j=1;j<=n;j++)
			if(!f[j]&&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]&&dis[j]<dis[k]*a[k][j])dis[j]=dis[k]*a[k][j];
	}
}
int main(){
	input();
	dj();
	printf("%0.8lf",100/dis[y]);
	return 0;
}
2023/8/9 15:25
加载中...