rt

机房大佬朴素dij都能过我堆优化还t飞了 抱头蹲防

#include <bits/stdc++.h>
using namespace std;
int head[100010];//表头 
int ver[100010];//右节点 
double edge[100010];//边权值 
int nxt[100010];//第一个与它相连的点的下标
int tot(0);
int vis[100010]; 
double dis[100010];
int n,m;
int a,b;
priority_queue<pair<double,int>,vector<pair<double,int> >,less<pair<double,int> > > q;
/*一维距离，二维编号*/
inline void add(int x,int y,int z) 
{
	ver[++tot]=y;
	edge[tot]=double(1.0-z/100.0);
	nxt[tot]=head[x];
	head[x]=tot;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z); 
	}
	cin>>a>>b;
	dis[b]=1.0;
	q.push(make_pair(1.0,b));
	while(!q.empty())
	{
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=nxt[i])
		{
			int y=ver[i];
			double z=edge[i];
			if(dis[y]<dis[x]*z)
			{
				dis[y]=dis[x]*z;
				q.push(make_pair(dis[y],y));
			}
			
		}
	}
	double ans=100.0/dis[a];
	cout<<fixed<<setprecision(8)<<ans;
	return 0;
}