【题解】B4292 [蓝桥杯青少年组省赛 2022] 路线

stellall · 2025-04-03 17:23:14 · 题解

题目大意

• 计算从每个景点，到游客服务中心的最短路径长度，即计算：编号 1 至 N-1 到编号 N 的距离。如果某个景点无法到达服务中心，则输出 -1。

• 这是一个典型的单源最短路径问题（By Oi-Wiki），适合使用广搜来做，但本人是个蒟蒻，所以我们用深搜来做。

解题思路

这时候就有人要问了：“主播，主播，如何表示图呢？”

• 由于邻接表可以表示图中两个顶点之间的连接关系，所以我们使用邻接表来存储景点之间的关系。因为路线是双向的，所以需要在邻接表中添加双向边。

这时候就又有人要问了：“主播，主播，如何计算短路径计算呢？”

• 我们从服务中心（编号 N）开始深搜遍历整个图，不断记录每个景点到服务中心的最短距离。

这时候就还是会有人问了：“主播，主播，这样深搜不会超时吗？”

• 如果是暴力深搜，那肯定会超时。但进行剪枝，即减少循环次数，就不会超时了。

• 我们使用栈（By Oi-Wiki）来实现深搜的非递归版本，避免递归深度过大而导致的超时。

代码流程

1. 初始化距离数组。用数组 dist 记录每个景点到服务中心的最短距离，初始时设为无穷大（用 0x3f3f3f3f 表示），服务中心自身距离设为 0。

2. 遍历与更新。从服务中心开始向四周遍历，每次访问相邻节点时，更新其最短距离。如果发现更短的路径，则更新距离并继续遍历。

参考代码

提交记录

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;//表示不可达

int main()
{
    int N,M;
    cin>>N>>M;
    vector<vector<int>> adj(N + 1);//邻接表
    for (int i=0;i<M;i++)
    {
        int s,e;
        cin>>s>>e;
        adj[s].push_back(e);
        adj[e].push_back(s);//由于是无向图，双向添加
    }

    vector<int> dist(N + 1, INF);//存储最短距离
    dist[N]=0;//服务中心到自身的距离为0

    stack<int> st;
    st.push(N);//从服务中心开始DFS

    while (!st.empty()) 
    {
        int u=st.top();
        st.pop();
        for (int v:adj[u]) 
        {
            if (dist[u]+1<dist[v]) 
            {//如果找到更短的路径
                dist[v]=dist[u]+1;
                st.push(v);// 继续深入
            }
        }
    }

    for (int i=1;i<N;i++) 
    {
        if (i>1) 
            cout<<" ";
        if (dist[i]==INF) 
            cout<<-1;
        else 
            cout<<dist[i];
    }

    return 0;
}