题目
题解
求A到B经过手续费之后的到账100元的初始最大值。每经过一个节点都要*一个小数,只要保证乘的这个小数最大即可。
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=2010;
int n,m;
int start,target;
double dist[N],g[N][N];
bool st[N];
void dijstrka(){
dist[start]=1;
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[t]<dist[j])){
t=j;
}
}
st[t]=true;
for(int j=1;j<=n;j++) dist[j]=max(dist[j],dist[t]*g[t][j]);
}
}
int main(){
cin>>n>>m;
while(m--){
int a,b,c;
cin>>a>>b>>c;
double z=(100.0-c)/100;
g[a][b]=g[b][a]=max(z,g[a][b]);
}
cin>>target>>start;
dijstrka();
printf("%.8f\n",100/dist[target]);
return 0;
}