A star 部分

https://www.luogu.com.cn/blog/juruoforever/qian-tan-astar

A star的建模中对距离的叙述，从state到ed的估价是符合实际中的距离增长趋势和规律的,规划和实际情况差距越小,对搜索的优化效果更好

经验得知：

1，k短路中一般使用最短路作为估价函数
2，八数码中使用当前所有点位到目标状态对应点位的曼哈顿距离作为估价

T1 次短路水一下

https://www.luogu.com.cn/problem/P1491
建模：次短路模板，$a ~ star$ 削弱版
错点：
1，$double$的无穷大不是$0x3f$，而是$127$
2，注意估价函数在判断中的写法
3，注意重载运算符时要重载>，优先队列是使用大于号的
4，注意路径上的点只能经过一次，需要一个$st$数组去重，这也是$spfa$模板$70$的原因

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int N =205;
const int M=  4e4+9;
typedef pair<double,double>pdd;
int m,d,n;
pdd p[N];
int nxt[M],h[N],e[M],idx;
double w[M];
double f[N];
bool vis[N];


struct spp
{
    int num;
    double v;
};

struct node
{
    int id;
    double dis;
    bool st[205];
    node ()
    {
        memset(st,0,sizeof st);
    }
};

priority_queue<spp>spq;
priority_queue<node>pq;


//dist就是f(x），g就是估价，还要开一个vis数组判重，否则只有70分

bool operator < (const spp &x,const spp &y)
{
    return x.v > y.v;
}

bool operator < (const node &x,const node &y)
{
    return f[x.id]+x.dis > f[y.id]+y.dis;
}

void add(int x,int y,double z)
{
    nxt[++idx]=h[x];
    h[x]=idx;
    e[idx]= y;
    w[idx]=z;
}

double qd(pdd x,pdd y)
{
    double res= (double)(x.first- y.first)* (x.first- y.first);
    res+= (double)(x.second- y.second)* (x.second- y.second);
    return (double)sqrt(res);
}

void dij_path()
{
    memset(f,127,sizeof f);
    memset(vis,0,sizeof vis);
    f[n]=0;
    spq.push((spp){n,0});
    while (spq.size())
    {
        spp u= spq.top();
        spq.pop();
        if(vis[u.num])continue;
        vis[u.num]=1;
        for(int i=h[u.num];~i;i=nxt[i])
        {
            int j=e[i];
            if(f[j]>f[u.num]+w[i])
            {
                f[j]=f[u.num]+w[i];
                spq.push((spp){j,f[j]});
            }
        }
    }
}

void A_star()
{
    node x;
    x.dis=0;
    x.id=1;
    pq.push(x);
    int tot = 0;
    while (pq.size())
    {
        node u = pq.top();
        pq.pop();
        if(u.id==n)tot++;
        if(tot==2)
        {
            printf("%.2lf",u.dis);
            return ;
        }

        int id= u.id;
        for(int i=h[id];~i;i=nxt[i])
        {
            int j=e[i];
            if(u.st[j])continue;
            node y = u;
            y.st[j]=1;
            y.dis=y.dis+w[i];
            y.id=j;
            pq.push(y);
        }
    }
    puts("-1");
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i= 1;i<= n;i++)scanf("%lf%lf",&p[i].first,&p[i].second);
    rep(i,1,m)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b,qd(p[a],p[b]));
        add(b,a,qd(p[a],p[b]));
    }
    dij_path();
    A_star();
}

T2 八数码难题

这是一个数字版的，没有涉及字符串和方案输出，是把$0$作为可移动对象处理的

https://www.luogu.com.cn/problem/P1379

错误点：
2，注意一维状态转化为二维的时候$s[i]$记录的是，$i$数字的一维位置，很方便从一维位置中得到其行列作标
3，使用了一个结构体”“伪成员函数”，算是一个新语法，把$f(x)$的估价性的加入转化到了成员函数之内

struct date
{
    int s,w;
    /// s是状态现状    w 是当前步数加估价函数
    date (int s,int w):s(s),w(w+f(s)) {}

    bool operator < (const date &rhs)const
    {
        return w>rhs.w;
    }

};

第4行的大括号是不能被省略的，这是这个语法结束的标志，保证了这是一个结构体赋值函数

4，估价函数在内联函数里面被定义，外层出队的时候我们只需要减去原数的影响和加上新的一步
5，替换特定数位的这个函数也值得一看

(将十进制表示为$x$的数字的第$a$位和第$b$位互换)

int swap(int x,int a,int b)
{
    int s = get(x,a);
    int t = get(x,b);
    x-=s*pow10[a-1]+t*pow10[b-1];
    x+=s*pow10[b-1]+t*pow10[a-1];
    return x;
}

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
map<int,int>vis;
int ed;
int d[4]={-3,-1,1,3};
// -1 与后一位交换，+3 与上一行交换
int pow10[]=
{
    1,10,100,1000,10000,100000,1000000,10000000,100000000
};

int get(int x,int p)
{
    return int (x/pow10[p-1])%10; //获取p从右数的第p位
}

int isup(int x)
{
    return x<=3;
}

int isdown(int x)
{
    return x>=7;
}

int isright(int x)
{
    return x%3==0;
}

int isleft(int x)
{
    return x%3==1;
}

int swap(int x,int a,int b)
{
    int s = get(x,a);
    int t = get(x,b);
    x-=s*pow10[a-1]+t*pow10[b-1];
    x+=s*pow10[b-1]+t*pow10[a-1];
    return x;
}

int row(int x) //行号
{
    return (x-1)/3;
    ///位置从第一个开始，然而第三个也是第一行所以减去一个偏移量
}

int col(int x) //列号
{
    return (x-1)%3;
    ///位置从第一个开始，然而第4个也是第一列所以减去一个偏移量
}

int f(int state)
{
    int s[20];
    int t[20];
    memset(s,0,sizeof s);
    memset(t,0,sizeof t);
    int ans = 0;
    ///获取状态中每个数字的位置
    rep(i,1,9)s[get(state,i)]=i,t[get(ed,i)]=i;
    rep(i,1,8)
    {
        ans+=abs(row(s[i])-row(t[i]))+abs(col(s[i])-col(t[i]));
    }
    return ans;
}

struct date
{
    int s,w;
    /// s是状态现状    w 是当前步数加估价函数
    date (int s,int w):s(s),w(w+f(s)) {}

    bool operator < (const date &rhs)const
    {
        return w>rhs.w;
    }

};

priority_queue<date>q;

int main()
{
    ed = 123804765;
    int s;
    cin>>s;
    q.push(date(s,0));
    vis.clear();
    while(q.size())
    {
        int p;
        date u =q.top();
        q.pop();
        if(vis[u.s])continue;
        if(u.s==ed)
        {
            cout<<u.w;
            return 0 ; ///这一步是灵魂，不然就不能达到优化效果了
        }
        vis[u.s]=1;
        rep(i,1,9)
        {
            int x= get(u.s,i);
            if(!x)
            {
                p=i; ///获得了0的位置
                break;
            }
        }
        rep(i,0,3)
        {
            if(i==0&&isup(p))continue;
            if(i==1&&isleft(p))continue;
            if(i==3&&isdown(p))continue;
            if(i==2&&isright(p))continue;

            int pp= p+d[i]; ///这里的更换方法决定了为什么要判断上下左右一类
            int t= swap(u.s,p,pp);
            q.push(date(t,u.w-f(u.s)+1));
            /// 估价函数在内联函数里面被定义，外层我们只需要减去原数的影响和加上新的一步
        }
    }
}