Bellman O(nm)能过......

#include<bits/stdc++.h>
using namespace std;
const int N=2001,M=200001;
int n,m,a,b;
int u,v;
double w;
struct ed {
	int u,v;
	double w;
} e[M];
int len=0;
double dis[N];
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++) {
		scanf("%d%d%lf",&u,&v,&w);
		w=1.0-w*0.01;
		e[++len]= {u,v,w};
		e[++len]= {v,u,w};
	}
	scanf("%d%d",&a,&b);
	for(int i=1; i<=n; i++) {
		dis[i]=9999999.0;
	}
	dis[b]=100.0;
	for(int i=2; i<=n; i++) {
		for(int j=1; j<=len; j++) {
			dis[e[j].v]=min(dis[e[j].v],dis[e[j].u]/e[j].w);
		}
	}
	printf("%.8lf",dis[a]);
	return 0;
}