D65 最短路 Dijkstra 算法

// 最短路 Dijkstra 算法 O(mlogn)
#include<bits/stdc++.h>
using namespace std;

const int N=2005;
int n,m,s,t;
vector<pair<double,int>> e[N];
int vis[N];
double d[N];

void dijkstra(){
  priority_queue<pair<double,int>> q; //大根堆
  q.emplace(d[s]=1,s);
  while(q.size()){
    int u=q.top().second; q.pop();
    if(vis[u]) continue; 
    vis[u]=1;
    for(auto [w,v]:e[u]){
      if(d[v]<d[u]*w) 
        q.emplace(d[v]=d[u]*w,v); //d[v]从s到v的最大汇率
    }
  }
}
int main(){
  cin>>n>>m;
  for(int i=0,x,y,z; i<m; i++){
    cin>>x>>y>>z;
    double p=(100.0-z)/100; //汇率
    e[x].emplace_back(p,y);
    e[y].emplace_back(p,x);
  }
  cin>>s>>t;
  dijkstra(); //计算汇率的最长路
  printf("%.8lf\n",100/d[t]); //汇率最大，费用最小
}