记录编号	221870	评测结果	AAAAAAAAAA
题目名称	最小花费	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.151 s
提交时间	2016-01-26 12:15:01	内存使用	3.39 MiB

#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 2005,maxm = 200050;
struct edge{
	int next,to;
	double w;
}lst[maxm];
int len = 1,n,m;
int first[maxn];
void insert(int v1,int v2,int cost){
	lst[len].to = v2;
	lst[len].w  = (100-cost)/100.0;
	lst[len].next = first[v1];
	first[v1] = len++;
}
double dis[maxn];
bool vis[maxn];
struct node{
	int to;
	double w;
	bool operator < (const node & a)const{
		return w<a.w;
	}
	node(int _to,double _w){
		to = _to;w = _w;
	}
}; 
void dij(int s){
	priority_queue<node> q;
	q.push(node(s,1.0));
	while(!q.empty()){
		while(!q.empty()&&vis[q.top().to])q.pop();
		if(q.empty())break;
		int j = q.top().to;
		dis[j] = q.top().w;
		vis[j] = true;
		q.pop();
		for(int pt = first[j];pt;pt = lst[pt].next){
			if(!vis[lst[pt].to])q.push(node(lst[pt].to,dis[j]*lst[pt].w));
		}
	}
}
int main(){
	freopen("moneyb.in","r",stdin);
	freopen("moneyb.out","w",stdout);
	scanf("%d %d",&n,&m);
	int a,b,c;
	for(int i = 0;i<m;++i){
		scanf("%d %d %d",&a,&b,&c);
		insert(a,b,c);
		insert(b,a,c);
	}
	scanf("%d %d",&a,&b);
	dij(a);
	printf("%.8lf\n",100/dis[b]);
	fclose(stdin);fclose(stdout);
	return 0;
}