P6245 [USACO06OPEN]The Climbing Wall S

_0x46EDC · 2020-08-09 11:04:37 · 题解

获得更好的阅读体验 题目传送门

题目分析

可以看作一张 01 权无向图，结点是落脚点，只要两个落脚点的距离不大于 1000 就连一条边。

对于起点和终点的处理，可以使用 虚拟结点 进行处理，即人为生成一个本来不存在的结点。

然后就可以用 Dijkstra 求单源最短路了。

接下来结合样例进行详细分析。

样例输入：

3000 5

600 800

1600 1800

100 1300

300 2100

1600 2300

样例输出：

3

Step1. 建图

• 对于距离 \le1000 的两个点，连一条权为 1 的边，代表经过这一条边次数加一。

• 处理起点。生成编号为 0 的虚拟结点，连接所有 y_i\le1000 的结点，即 1 号结点。注意边权为 0 ，代表不需要计算次数。

• 处理终点。生成编号为 f+1 的虚拟结点，连接所有 h-y_i\le1000 的结点，即 4 号结点和 5 号结点。

求从 0 号结点到 f+1 号结点的最短距离，可得答案 3。

Step2. 求最短路

使用朴素版 Dijkstra 算法，几乎就是模板代码。

优化

为了缩短代码，我们也可以把这个问题简化为无权无向图。因为一定要从虚拟起点开始，可以将虚拟起点为端点的边权设为 1，输出答案时 -1 即可。

代码

#include<bits/stdc++.h>
#define N 100009
#define INF 0x3f3f3f3f
using namespace std;
vector<int> to[N];
int h,f,d[N];
struct pnt{
    double x,y;
}p[N];//定义结构体，保存每个点的x,y坐标
double dist(int a,int b){
    return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
}//求两点的欧几里得距离
void add(int u,int v){
    to[u].push_back(v);
    to[v].push_back(u);
}//建无向无权边
void build(){
    for(int u=1;u<=f;u++){
        for(int v=u+1;v<=f;v++){
            if(dist(u,v)<=1000)add(u,v);//如果两点距离不大于1000则建边
        }
        if(h-p[u].y<1000)add(u,f+1);//虚拟终点建边，代表可以一步走到终点
        if(p[u].y<=1000)add(0,u);//虚拟起点建边，代表起点
    }
}
void Dijkstra(){
    fill(d,d+f+9,INF);
    queue<int> q;
    d[0]=0;
    q.push(0);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=0;i<to[u].size();i++){
            int v=to[u][i];
            if(d[v]>d[u]+1){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
}//朴素版Dijkstra模板代码
int main(){
    cin>>h>>f;
    for(int i=1;i<=f;i++)cin>>p[i].x>>p[i].y;//保存每个结点的具体信息
    build();//建图
    Dijkstra();
    cout<<d[f+1]-1<<endl;//记得-1
    return 0;
}

结语

主要考察“虚拟结点”的运用，做完此题建议继续尝试其他图论题目。