RT。我的代码如下:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 5, MAXM = 1e5 + 5, inf = 1e10;
#define M(x, y) make_pair(x, y)
int n, m, s, t;
int tot;
int fr[MAXN], to[MAXM], nex[MAXM];
double val[MAXM], dis[MAXN];
bool vis[MAXN];
priority_queue<pair<double,int> > q;
void add(int x, int y, double z) {
to[++tot] = y;
val[tot] = z;
nex[tot] = fr[x];
fr[x] = tot;
}
void dijkstra() {
for (int i = 1; i <= n; i++) dis[i] = inf;
dis[s] = 1;
q.push(M(1, s));
while (!q.empty()) {
int x = q.top().second;
q.pop();
if (vis[x]) continue;
vis[x] = true;
for (int i = fr[x]; i; i = nex[i]) {
int y = to[i], z = val[i];
if (dis[x] * z > dis[y]) {
dis[y] = dis[x] + z;
q.push(M(dis[y], y));
}
}
}
}
int main() {
cin >> n >> m;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, 1 - w / 100.0);
add(v, u, 1 - w / 100.0);
}
cin >> s >> t;
dijkstra();
printf("%.8lf", 100 / dis[t]);
return 0;
}
不知道哪里错了,输出 0.00000005,求助大佬!