spfa算法
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=2010,M=1e6+10;
int h[N],e[M],ne[M],w[M],idx;
double d[N];
bool st[N];
int n,m;
void add(int a,int b,int c){
e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
double spfa(int l,int r){
queue<int> q;
q.push(l);
d[l]=1;
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(d[j]<=d[t]*0.01*w[i]){
d[j]=d[t]*0.01*w[i];
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
return d[r];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(;m;m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,100-c);
add(b,a,100-c);
}
int l,r;
cin>>l>>r;
printf("%.8lf",100/spfa(l,r));
return 0;
}