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;全部评论 (0)
还没有任何评论哟~