记录编号	566341	评测结果	AAAAAAAAAA
题目名称	最小花费	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.071 s
提交时间	2021-11-05 13:59:16	内存使用	4.23 MiB

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N=10005;
int st[N];
int mc,nc;
struct qxx
{
	double p;
	int ar;
	int nx;
}a[1000005];
int aj;
double n[N];
queue<int> l;
void js(int x,int y,double z)
{
	a[++aj].p=1-(z/100);
	a[aj].ar=y;
	a[aj].nx=st[x];
	st[x]=aj;
	return;
}
int nj[N];
void SPFA()
{
	int cl;
	while(!l.empty())
	{
		cl=l.front();
		l.pop();
		nj[cl]=0;
		for(int i=st[cl];i!=0;i=a[i].nx)
		{
			if(n[cl]*a[i].p>n[a[i].ar])
			{
				n[a[i].ar]=n[cl]*a[i].p;
				if(nj[a[i].ar]==0)
				{
					l.push(a[i].ar);
				    nj[a[i].ar]=1;
				}
			}
		}
	}
	return;
}
int main()
{
	freopen("moneyb.in","r",stdin);
	freopen("moneyb.out","w",stdout);
    cin>>mc>>nc;
    int s1,s2;
    double s3;
    for(int i=1;i<=nc;i++)
    {
    	scanf("%d%d%lf",&s1,&s2,&s3);
    	js(s1,s2,s3);
    	js(s2,s1,s3);
    }
//    for(int i=1;i<=nc;i++)
//    {
//    	cout<<"i:"<<i<<endl;
//    	for(int o=st[i];o!=0;o=a[o].nx)
//    	{
//    		cout<<a[o].ar<<" "<<a[o].p<<endl;
//    	}
//    }
    scanf("%d%d",&s1,&s2);
    n[s1]=1;
    nj[s1]=1;
    l.push(s1);
    SPFA();
    s3=100/n[s2];
    printf("%.8lf\n",s3);
//    printf("%lf\n",n[1]);
	return 0;
}