样例过了0分求调dij带优化
查看原帖
样例过了0分求调dij带优化
602624
___njr___楼主2023/8/20 21:58
#include<bits/stdc++.h>
using namespace std;
#define _Ty double
#define maxn 2023
#define inf 1e9
#define max(a,b) ((a)>(b)?(a):(b))
struct Node
{
    int x;
    _Ty dis;
    bool operator >(const Node& a)const
    {
        if (dis == a.dis) return x < a.x;
        return dis > a.dis;
    }
};
#define node Node
    priority_queue <node, vector<node>, greater<node>> q;
    typedef pair<int, _Ty> pii;
    vector <pii> e[maxn+10];
    int n, m, s, day[maxn];
    _Ty dis[maxn];
    bool vis[maxn];
#undef node
inline void dijstra() {
    for (int i = 1; i <= n; ++i)dis[i] =1e-38;
    dis[s] = 1;
    q.push({ s,0.0 });
    while (!q.empty())
    {
        int temp = q.top().x;
        q.pop();
        if (vis[temp]) continue;
        vis[temp] = true;
        for (auto to : e[temp])
        {
            dis[to.first] = max(dis[to.first], dis[temp] * to.second);
            q.push({ to.first,dis[to.first] });
        }
    }
}
//}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    
    for (int i = 0; i < m; ++i) {
        int u, v, z;
        cin >> u >> v >> z;
        double w = (double)(100 - z) * 0.01;
        e[u].push_back(make_pair(v, w));
        e[v].push_back(make_pair(u, w));
    }
    int b;
    cin >> s>>b;
    dijstra();
    printf("%lld.%.8lld", (long long)(100 / dis[b]), (long long)(10000000000 / dis[b]) % 100000000);
    return 0;
}

task1~10没过,求调

2023/8/20 21:58
加载中...