测了样例,输出 $103.09278351$。
by _tanzk_ @ 2023-07-13 12:16:35
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int h[N], vtx[2 * N], nxt[2 * N], idx;
double dis[N], wt[2 * N];
int pre[N], vis[N];
int n, m, s, t, tu, tv;
double tw;
struct node {
int u, v;
double w;
friend bool operator < (node a, node b) {
if (a.w >= b.w) {
return 1;
} else {
return 0;
}
}
};
priority_queue <node> q;
void addEdge(int a, int b, int c) {
vtx[idx] = b;
nxt[idx] = h[a];
wt[idx] = 1.0 - c / 100.0;
h[a] = idx++;
}
void dijkstra(int s) {
dis[s] = 1.0;
node tmp;
tmp.u = s;
tmp.v = s;
tmp.w = 1.0;
q.push(tmp);
while (!q.empty()) {
tmp = q.top();
q.pop();
int nid = tmp.v;
if (vis[nid] == 1) {
continue;
}
vis[nid] = 1;
int p = h[nid];
while (p != -1) {
if (vis[vtx[p]] == 0) {
if (dis[nid] * wt[p] > dis[vtx[p]]) {
dis[vtx[p]] = dis[nid] * wt[p];
pre[vtx[p]] = nid;
tmp.u = nid;
tmp.v = vtx[p];
tmp.w = dis[vtx[p]];
q.push(tmp);
}
}
p = nxt[p];
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
dis[i] = 0;
}
memset(h, -1, sizeof(h));
while (m--) {
cin >> tu >> tv >> tw;
addEdge(tu, tv, tw);
addEdge(tv, tu, tw);
}
cin >> s >> t;
dijkstra(s);
cout << fixed << setprecision(8) << 100.0 / dis[t];
return 0;
}
```
by _tanzk_ @ 2023-07-13 20:45:24