记录编号	581605	评测结果	AAAAAAAAAA
题目名称	最小花费	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.074 s
提交时间	2023-08-08 12:24:53	内存使用	1.76 MiB

#include <bits/stdc++.h> 
using namespace std;
//最短路变形
//做法:dij.. 
typedef pair<double,int> P;
const int N = 2010,M = 200010;
int n,m,s,t;
struct made{
	int ver,nx;
	double ed;
}e[M];
int hd[N],tot;
double d[N];
bool v[N];
void add_(int x,int y,double z){
	tot++;
	e[tot].ver = y,e[tot].ed = z,e[tot].nx = hd[x],hd[x] = tot;
}
void dij(int x){
	memset(v,0,sizeof(v));
	//memset(d,-0x3f,sizeof(d));
	priority_queue<P,vector<P>,less<P> >q;//大根堆!!! 
	d[x] = 1;
	q.push(make_pair(0,x));
	while(!q.empty()){
		int x = q.top().second;q.pop();
		if(v[x])continue;
		v[x] = 1;
		for(int i = hd[x];i;i = e[i].nx){
			int y = e[i].ver;double z = e[i].ed;
			if(d[x] * z > d[y]){
				d[y] = d[x] * z;
				q.push(make_pair(d[y],y));
			}
		}
	}
}
int main(){
	freopen("moneyb.in","r",stdin);
	freopen("moneyb.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++){
		int x,y;double z;
		scanf("%d%d%lf",&x,&y,&z);
		z = (100-z)/100.0;
		add_(x,y,z);
		add_(y,x,z);
	}
	scanf("%d%d",&s,&t);
	dij(s);
    printf("%.8lf\n",100.0/d[t]);
	
	return 0;
	
}