这题我A星算法只得60分,不知道错哪了
查看原帖
这题我A星算法只得60分,不知道错哪了
1069719
Enoch2013楼主2024/5/10 22:10
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
struct edge
{
    int from, to;
    double w;
    edge(int a, int b, double c)
    {
        from = a;
        to = b;
        w = c;
    }
};
vector<edge> e[N];
typedef pair<double, int> PII;
typedef pair<double, PII> PI;
int n, m, x, y, z, s, t;
double dis[N];
double h[N];
bool vis[N];
bool f[N];
double minx = 1e9;

void dijkstra(){
    memset(h, 0x43, sizeof(h));
    priority_queue<PII, vector<PII>, greater<PII> > heap;
    h[s] = 1;
    heap.push(PII(h[s], s));
    while(!heap.empty()) {
        PII pii = heap.top();
        heap.pop();
        int p = pii.second, d = pii.first;
        if(f[p]) continue;
        f[p] = true;
        if(p == t) return;
        for(int i = 0; i < e[p].size(); i++){
            int to = e[p][i].to;
            double ww = d / e[p][i].w;
            if(ww < h[to]){
                h[to] = ww;
                // cout << to << ' ' << h[to] << endl;
                heap.push(PII(h[to], to));
            }
        }
    }
}

void astar()
{
    memset(dis, 0x43, sizeof(dis));
    dis[t] = 100;
    priority_queue<PI, vector<PI>, greater<PI> > q;
    q.push(PI(dis[t], PII(dis[t], t)));
    while (!q.empty())
    {
        PI u = q.top();
        q.pop();
        int to = u.second.second;
        double to_dis = u.second.first;
        if(vis[to]) continue;
        vis[to] = true;
        if (to == s) return;
        for (int i = 0; i < e[to].size(); i++)
        {
            edge y = e[to][i];
            if(vis[y.to]) continue;
            double d = to_dis * h[y.to] / y.w;
            dis[y.to] = to_dis / y.w;
            // cout << d << " " << dis[y.to] << endl;
            q.push(PI(d, PII(dis[y.to], y.to)));
        }
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &x, &y, &z);
        e[x].push_back(edge(x, y, 1 - z * 1.0 / 100));
        e[y].push_back(edge(y, x, 1 - z * 1.0 / 100));
    }
    scanf("%d %d", &s, &t);
    dijkstra();
    astar();
    printf("%.8lf", dis[s]);
    return 0;
}
2024/5/10 22:10
加载中...