题解 P6245 【[USACO06OPEN]The Climbing Wall S】

· · 题解

题解 P6245 【The Climbing Wall S】

核心算法：最短路

1.建模

我先来把问题简述一下： 在一个平面内，每个点都有其横坐标与纵坐标。Bessie想要从一个纵坐标不超过1000的点，爬到一个纵坐标为题目给定的H的点上。她每一步可以爬到与当前点距离不超过1000的点。问：最少爬多少步？

我们把题目中每一个落脚点就看作图中的点，把可以直接到达的两个点间建一条权值为1的边，代表走了一步。

那么跑一遍最短路，到终点的距离即为题目的答案。

2.细节

①建图

可能有些朋友已经注意到了，题目的起点和终点不唯一。

难道我们要跑多源最短路？那题目的数据范围显然是不允许的。

我们就要引入一种思想——虚拟点！

我自己乱起的名字

Bessie 的起点可以在任一高度不超过1000的落脚点上。

也就是说，所有纵坐标小于等于1000的点都可以作为起点。

那么我们可以建立一个虚拟起点，它到所有可以作为起点的点之间都建立一条边，权值为0（代表不增加次数）。这样，我们就可以以这个虚拟的起点为总起点跑单源最短路径了

但还有个问题，怎么确定终点呢？

一旦她到达了一个高度距离 H 不到 1000 的落脚点，可以直接到墙顶。

很容易理解，墙顶就是我们的终点，但并不是一个横纵坐标都确定的点。那么，我们就可以自己把它建立出来！

所有纵坐标距离最大高度H不到1000的点我们都连上虚拟终点，是不是问题就简单了？

②距离处理

我相信这个其实不用说，你们也知道。

欧几里得距离公式：

\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}

③最短路

剩下的就是最短路模板了。

关于跑最短路，我还是秉持我一贯的观点：只要没有负边权，就用Dijkstra+堆优化。

关于SPFA，它死了

3.代码实现

我们前面一直只是纸上谈兵，那关键的操作如何实现呢？

很多朋友最短路相关问题，点和边的下标都是从1开始的。那么我们正好可以把0作为虚拟起点，把f+1作为虚拟终点。也很好理解不是吗？

当然也有朋友下标从0开始，其实把f+1作为虚拟起点，把f+2作为虚拟终点，也完全OK。

具体请见代码注释。

#include<cmath>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#define pii pair<int,int>//宏定义，个人习惯
using namespace std;
struct Node
{
    int head,dis;
    double x,y;
    //横坐标和纵坐标
}node[10005];
struct Edge
{
    int next,to,len;
}edge[99990005];
int h,f;
//与题目意义相同
bool cmp(Node a,Node b)
{
    if(a.y==b.y)return a.x<b.x;
    return a.y<b.y;
}
//排序函数，方便对点进行处理
double calc(double x_1,double y_1,double x_2,double y_2)
{
    return double(sqrt((x_1-x_2)*(x_1-x_2)+(y_1-y_2)*(y_1-y_2)));
}
//求距离
int cnt;
void addEdge(int u,int v,int w)
{
    edge[++cnt].len=w;
    edge[cnt].next=node[u].head;
    edge[cnt].to=v;
    node[u].head=cnt;
}
//链式前向星存图
void Dijkstra()
{
    for(int i=0;i<=f+1;i++) node[i].dis=0x3f3f3f3f;
    //别忘了初始化
    priority_queue<pii,vector<pii>,greater<pii> >q;
    //STL小根堆
    node[0].dis=0;
    q.push({0,0});
    while(q.size())
    {
        pii tmp=q.top();
        q.pop();
        int d=tmp.first,u=tmp.second;
        if(d!=node[u].dis)continue;
        for(int e=node[u].head;e;e=edge[e].next)
        {
            int v=edge[e].to;
            if(node[v].dis>d+edge[e].len)
            {
                node[v].dis=d+edge[e].len;
                q.push({node[v].dis,v});
            }
        }
    }
}
//模板
int main()
{
    scanf("%d%d",&h,&f);
    for(int i=1;i<=f;i++)
    {
        scanf("%lf%lf",&node[i].x,&node[i].y);
    }
    sort(node+1,node+f+1,cmp);
    //排序
    for(int i=1;i<=f;i++)
    {
        for(int j=i+1;j<=f;j++)
        {
            double dist=calc(node[i].x,node[i].y,node[j].x,node[j].y);
            //求得距离
            if(dist<=1000)
            {
                //如果两个点间的距离不超过1000,
                //就可以直接到达
                //建立权值为1的边
                //表示爬一次
                addEdge(i,j,1);
                addEdge(j,i,1);
            }
        }
        if(h-node[i].y<1000)
        {
            //与最大距离H不到1000的点可以直接到达终点
            //那么就与虚拟终点连一条边
            addEdge(i,f+1,1);
            addEdge(f+1,i,1);
            //虚拟终点就是f+1
        }
        if(node[i].y<=1000)
        {
            //与地面距离不超过1000的点可以作为起点
            //那么就与虚拟起点连一条边
            addEdge(0,i,0);
            addEdge(i,0,0);
            //虚拟起点就是0
        }
    }
    Dijkstra();
    printf("%d\n",node[f+1].dis);
    //这里注意输出的是虚拟终点的距离
    return 0;
}

那么，题解到这里就结束了！

写题解不易，希望大家多多支持。如果还有不懂的可以at我或者私信我，我会尽力帮助的！