解题报告 P2901 [USACO08MAR]Cow Jogging G

题目内容

P2901

给定一有向带权图,求从 n 到 1 的前 k 短路的长度

解题思路

求 k 短路的一个常用的方法是使用 A*,怎么求呢?

首先,预处理出所有点到 1 的最短距离(使用反向图跑最短路),然后从 n 开始进行广搜,只不过队列改为优先队列,估价方式为 f+dis[now] 小的先出队,其中 f 为已经走过的路,dis[now]now 到 1 的最短距离,这样子进行估价可以使估的价一定小于等于实际代价。然后 A* 会根据估价从小到大依次进行扩展,最先进入到 1 号的就是最短路,随后次短路,第三短路。。。会依次进入到 1 号点,每次输出走过路径长即可。

#include <queue>
#include <cstdio>
#include <vector>
#include <cctype>
#include <utility>
#include <cstring>

typedef long long ll;
using namespace std;

const int maxn=1e3+5;

struct node
{
    ll pos,f;
    node(){}
    node(int _p,int _f)
    {
        pos=_p;
        f=_f;
    }
};

struct edge
{
    ll from,to,dist;
    edge(){}
    edge(ll u,ll v,ll w)
    {
        from=u;
        to=v;
        dist=w;
    }
};

//快读省略

vector<edge> g1[maxn],g2[maxn];//g1存正向图,g2存反向图
ll dis[maxn],n,m,k;
bool vis[maxn];

bool operator<(const node &_a,const node &_b)
{
    return _a.f+dis[_a.pos]>_b.f+dis[_b.pos];
}

void dijsktra()//反向跑dij获取每个点的距离
{
    priority_queue<pair<ll,ll>, vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
    memset(dis,0x3f,sizeof(vis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(auto &e:g2[now])
            {
                if(dis[e.to]>dis[now]+e.dist)
                {
                    dis[e.to]=dis[now]+e.dist;
                    q.push(make_pair(dis[e.to],e.to));
                }
            }
        }
    }
    return;
}

void astar()//开始A*
{
    priority_queue<node> q;
    q.push(node(n,0));
    while(!q.empty())
    {
        ll now=q.top().pos,f=q.top().f;
        q.pop();
        if(now==1)//如果到终点了
        {
            printf("%lld\n",f);//直接输出
            if(!(--k))//如果已经求完前k短路,结束
                return;
        }
        else
            for(auto i:g1[now])//然后就是扩展
                q.push(node(i.to,i.dist+f));
    }
    while(k--)//如果还有没搞完的
        printf("-1\n");
    return;
}

inline void ins(ll u,ll v,ll w)
{
    g1[u].push_back(edge(u,v,w));
    g2[v].push_back(edge(v,u,w));
    return;
}

int main()
{
    n=read(),m=read(),k=read();
    ll u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        ins(u,v,w);
    }
    dijsktra();
    astar();
    return 0;
}

解题报告 P5507 机关

题目内容

P5507

大意:这扇门上有一个机关,上面一共有12个旋钮,每个旋钮有4个状态,将旋钮的状态用数字1到4表示

每个旋钮只能向一个方向旋转(状态:1->2->3->4->1),在旋转时,会引起另一个旋钮也旋转一次(方向相同,不会引起连锁反应),同一旋钮在不同状态下,可能会引起不同的旋钮旋转(在输入中给出)

当所有旋钮都旋转到状态1时,机关就打开了

求最少打开门的次数

解题思路

搜索,但是由于极高的复杂度,肯定是不能用一般的搜索的。

然后可以使用 A*,卡卡常可以过去,A* 的估价函数设为当前步数加上旋钮与 1 差的步数之和除以二向上取整。因为考虑最优情况:转一个旋钮可以带动两个,所以这个估价函数是比较不错的。

A* 的实现使用优先队列即可,好像这题吸氧没什么卵用

判重由于我不写 hash,就搞了个 12 维的 bool 数组,计算器告诉我们空间能过(好了我要滚去学状态优化了)。

其实这题还可以用双向 bfs,因为初始状态和终止状态都是已知的

复杂度 O(玄学)

代码:

#include <cstdio>
#include <cctype>
#include <queue>
#define vis(x) (v[x.s[1]%4][x.s[2]%4][x.s[3]%4][x.s[4]%4][x.s[5]%4][x.s[6]%4][x.s[7]%4][x.s[8]%4][x.s[9]%4][x.s[10]%4][x.s[11]%4][x.s[12]%4])
using namespace std;

struct node
{
    int q[19];
    int s[13];
    int step;
    int chk;
};

inline void nxt(int &a)//将这个旋钮转一下
{
    a=(a+1)%4==0?4:(a+1)%4;
    return;
}

inline int read()
{
    char c=getchar();
    int s=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
        s=10*s+c-'0',c=getchar();
    return s;
}

int a[13][5];
bool v[4][4][4][4][4][4][4][4][4][4][4][4];//巨长的 vis 数组

inline int h(node &x)//估价函数
{
    int ans=0;
    for(int i=1;i<=12;i++)
        ans+=x.s[i]==1?0:5-x.s[i];
    return (ans-1>>1)+1;
}

inline int check(node &x)//检查是否到达了最终状态
{
    for(int i=1;i<=12;i++)
        if(x.s[i]!=1)
            return false;
    return true;
}

bool operator>(const node &a,const node &b)//重载大于号
{
    return a.chk>b.chk;
}

void astar(node st)
{
    priority_queue<node,vector<node>,greater<node> > q;
    q.push(st);
    while(!q.empty())
    {
        node now=q.top();
        q.pop();
        if(check(now))
        {
            printf("%d\n",now.step);
            for(int i=1;i<=now.step;i++)
                printf("%d ",now.q[i]);
            return;
        }
        if(vis(now))
            continue;
        else
        {
            vis(now)=1;
            node nextone=now;
            for(int i=1;i<=12;i++)//状态转移
            {
                nxt(nextone.s[a[i][nextone.s[i]]]);
                nxt(nextone.s[i]);
                nextone.q[++nextone.step]=i;
                nextone.chk=h(nextone)+nextone.step;
                q.push(nextone);
                nextone.s[i]=now.s[i];
                nextone.s[a[i][nextone.s[i]]]=now.s[a[i][nextone.s[i]]];
                nextone.step--;
            }
        }
    }
}

int main()
{
    node st;
    for(int i=1;i<=12;i++)
    {
        for(int j=0;j<=4;j++)
            a[i][j]=read();
        st.s[i]=a[i][0];
    }
    st.chk=h(st);
    st.step=0;
    astar(st);
    return 0;
}