求助堆优 Dijkstra 写最小花费
  • 板块学术版
  • 楼主liuzimingc
  • 当前回复8
  • 已保存回复8
  • 发布时间2021/8/7 07:47
  • 上次更新2023/11/4 11:45:52
查看原帖
求助堆优 Dijkstra 写最小花费
421781
liuzimingc楼主2021/8/7 07:47

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,求助大佬!

2021/8/7 07:47
加载中...