AcWing 1126. Minimum cost solution (shortest path Dijkstra)

AcWing 1126. Minimum cost
Plain version dijkstra Algorithm for the shortest path , Familiar with the template again , Pay attention to the meaning of the question , You need to convert the given value into a loss rate , Then apply the shortest path model to calculate the product of the loss rate of the path with the largest product of the loss rate （ Why should we maximize the product of the loss rate? See the following formula ：）

#include<bits/stdc++.h>

using namespace std;

#define db double

const int N = 2100, M = 2e5 + 10;

db g[N][N];
db d[N];
int n, m;
int S, T;
bool st[N];

void dijkstra(){
    
	d[S] = 1;
	
	for(int i = 1; i <= n; i ++ ){
    
		int t = -1;
		for(int j = 1; j <= n; j ++ ){
    
			if(!st[j] && (t == -1 || d[t] < d[j])) t = j;
		}
		st[t] = true;
		for(int j = 1; j <= n; j ++ ){
    
			d[j] = max(d[j], d[t] * g[t][j]);
		}
	}
}

int main()
{
    
	cin>>n>>m;
	while(m -- ){
    
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		db z = (100.0 - c) / 100;  // Special treatment , Convert the deducted money directly into the discount rate , The meaning of the question is to transform it into the road with the greatest loss rate , Or the shortest path model  
		g[a][b] = g[b][a] = max(g[a][b], z);  
	}
	
	cin>>S>>T;
	
	dijkstra();
	
	printf("%.8lf\n", 100 / d[T]);

	return 0;
}