AcWing 1126. 最小花费 题解（最短路—dijkstra）

AcWing 1126. 最小花费
朴素版dijkstra算法求最短路，又熟悉了一遍模板，注意题意，需要将给出的值转化成折损率，之后套用最短路模型求出折损率之积最大的一条路的折损率之积（为什么要折损率之积最大见如下公式：）

#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;  //特殊处理，将扣的钱直接转化为折损率，题意即转化成折损率成绩最大的一条路，还是最短路模型 
		g[a][b] = g[b][a] = max(g[a][b], z);  
	}
	
	cin>>S>>T;
	
	dijkstra();
	
	printf("%.8lf\n", 100 / d[T]);

	return 0;
}