题解 P2483 【[SDOI2010]魔法猪学院】

Orion_Rigel · 2016-09-30 00:24:10 · 题解

A*算法，估价函数就是反向图的到终点的最短路长度，注意精度处理。

···

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const double eps=1e-7;
int h[5001],ne[400001],to[400001],en=0;
double w[400001],f[5001],e;
int inq[5001],n,m,ans=0;
struct node{
    int now;
    double step;
    double g;
    bool operator < (node x) const{
        return (g==x.g)?step>x.step:g>x.g;
    }
};
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void add(int a,int b,double c)
{ne[en]=h[a];to[en]=b;w[en]=c;h[a]=en++;}
inline void SPFA1()
{
    memset(f,127,sizeof f);
    f[n]=0;inq[n]=1;
    queue<int>q;
    q.push(n);
    while (!q.empty())
    {
        int x=q.front();q.pop();inq[x]=0;
        for (register int i=h[x];i>=0;i=ne[i])
        if (i&1){
            if (f[to[i]]>f[x]+w[i])
            {
                f[to[i]]=f[x]+w[i];
                if (!inq[to[i]])
                {
                    inq[to[i]]=1;
                    q.push(to[i]);
                }
            }
        }
    }
}
inline void Astar()
{
    priority_queue<node>q;
    node S;
    S.now=1;
    S.step=0;
    S.g=S.step+f[S.now];
    q.push(S);
    while (!q.empty()&&(e+eps>0))
    {
        node x=q.top();q.pop();
        if (x.now==n)
        {
            if (e-x.step+eps>0) ans++,e-=x.step;
            else e=-100;
        }
        if (x.g>e) break;
        for (register int i=h[x.now];i>=0;i=ne[i])
        if (!(i&1)){
            node next;
            next.now=to[i];
            next.step=x.step+w[i];
            next.g=next.step+f[next.now];
            if (next.g>e) continue;
            q.push(next);
        }
    }
}
int main()
{
    memset(h,-1,sizeof h);
    n=read();m=read();
    scanf("%lf",&e);
    for (register int i=1;i<=m;++i)
    {
        int a,b;
        double c;
        a=read();b=read();
        scanf("%lf",&c);
        add(a,b,c);
        add(b,a,c);
    }
    SPFA1();
    Astar();
    printf("%d\n",ans);
}
···