记录编号	322973	评测结果	AAAAAAAAAA
题目名称	最小花费	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.249 s
提交时间	2016-10-15 19:49:56	内存使用	17.93 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=500010;
struct edge{int f,t;double l;}w[N];
int n,m,head[N],tail[N],next[N];
inline void add(int f,int num){
	if (!head[f]) head[f]=tail[f]=num;
		else tail[f]=next[tail[f]]=num;
}
double dis[N];bool vis[N];
int main()
{
	freopen("moneyb.in","r",stdin);
	freopen("moneyb.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d%lf",&w[i].f,&w[i].t,&w[i].l);
		w[i].l=(100-w[i].l)/100;
		w[i+m]=w[i];swap(w[i].f,w[i].t);
		add(w[i].f,i);add(w[i].t,i+m);
	}
	int s,t;
	scanf("%d%d",&s,&t);
	for (int i=1;i<=n;i++) dis[i]=1e+9;
	dis[s]=100;
	while (1){
		int v=0;
		for (int i=1;i<=n;i++)
		if (!vis[i]&&(!v||dis[i]<dis[v])) v=i;
		if (!v) break;
		vis[v]=1;
		for (int i=head[v];i;i=next[i])
		if (dis[w[i].t]>dis[v]/w[i].l)
			dis[w[i].t]=dis[v]/w[i].l;
	}
	printf("%.8lf\n",dis[t]);
	return 0;
}