AcWing 1126. 最小花费-全负权边图 Dijikstra 求最短路
原题链接
简单
作者:
KeChang
,
2023-10-01 11:17:17
,
所有人可见
,
阅读 50
#include <iostream>
#include <bitset>
using namespace std;
using DOU = double;
const int N = 2e3 + 10;
int n, m, s, e;
DOU dist[N], g[N][N];
bitset <N> st;
DOU dijkstra() {
dist[s] = 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] = 1;
for (int j = 1; j <= n; ++j)
dist[j] = max(dist[j], dist[t] * g[t][j]);
}
return 100.0 / dist[e];
}
int main () {
cin >> n >> m;
while(m--) {
int a, b, c;
cin >> a >> b >> c;
DOU charge = (100 - c) / 100.0;
g[a][b] = g[b][a] = max(g[a][b], charge);
}
cin >> s >> e;
printf("%.8lf",dijkstra());
return 0;
}