求调!!!!!!!!!!
  • 板块P1576 最小花费
  • 楼主Xianzi_
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/10/19 16:01
  • 上次更新2024/10/19 17:40:23
查看原帖
求调!!!!!!!!!!
591561
Xianzi_楼主2024/10/19 16:01
#include "bits/stdc++.h"
using namespace std;
const int xzx = INT_MIN;
struct node{
    int id;
    double w;
    
};
bool operator< (node a, node b){
    return a.w > b.w;
};
int n, m, a, b;
double ans;
double dis[2010];
bool flag[2010];
vector <node> g[2010];
priority_queue <node> q;

void dijsktra(){
    for (int i = 0; i <= 2010; i++) dis[i] = xzx;
    dis[a] = 1.0;
    q.push({a, 1.0});
    while (!q.empty()){
        node u = q.top();
        q.pop();
        if (flag[u.id]) continue;
        flag[u.id] = 1;
        dis[u.id] = u.w;
        for (int i = 0; i < g[u.id].size(); i++)
            if (!flag[g[u.id][i].id] && (1.0 * u.w * g[u.id][i].w < dis[g[u.id][i].id]*1.0)){
                dis[g[u.id][i].id] = dis[u.id] * g[u.id][i].w;
                q.push({g[u.id][i].id, (1.0 * u.w * g[u.id][i].w)});
            }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int x, y;
        double z;
        cin >> x >> y >> z;
        g[x].push_back({y, (1.0 - 0.01 * z)});
        g[y].push_back({x, (1.0 - 0.01 * z)});
    }
    cin >> a >> b;
    dijsktra();
    ans = 100 / dis[b];
    printf("%.8lf\n", ans);
    return 0;
}
2024/10/19 16:01
加载中...