51nod 2600 小Biu的旅行

本文主要是介绍51nod 2600 小Biu的旅行，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

原题链接

51nod 2600
题目类型：$2$级题$♦♦$
AC记录：Accepted

题目大意

小Biu所在的城市有$n$个景点，有一些景点之间有单向联通的道路，现在小Biu在$1$号景点上，他想知道到达除了$1$号景点之外的每个景点分别最少需要经过多少条道路？

输入格式

第$1$行：两个正整数$n,m$，$n$表示景点的个数，$m$表示路径的条数。(1<=n<=1000,1<=m<=3000)
第$2$到$m+1$行：每行两个$u,v$，表示$u$到$v$有一条单向联通的道路,数据保证没有重边和自环。(1<=u,v<=n)

输出格式

输出$n-1$行，第$i$行表示从$1$号景点到达$i+1$号景点最少要经过几条道路，如果不能到达则输出$-1$。
$\mathbf{S}\mathbf{a}\mathbf{m}\mathbf{p}\mathbf{l}\mathbf{e}$ $\mathbf{I}\mathbf{n}\mathbf{p}\mathbf{u}\mathbf{t}$

6 6
1 2
1 3
2 4
3 2
3 5
5 6

$\mathbf{S}\mathbf{a}\mathbf{m}\mathbf{p}\mathbf{l}\mathbf{e}$ $\mathbf{O}\mathbf{u}\mathbf{t}\mathbf{p}\mathbf{u}\mathbf{t}$

1
1
2
2
3

$\mathbf{H}\mathbf{i}\mathbf{n}\mathbf{t}\&\mathbf{E}\mathbf{x}\mathbf{p}\mathbf{l}\mathbf{a}\mathbf{i}\mathbf{n}$
样例所示的图如下图所示。

数据范围

对于$100\%$的数据，$1\le n\le 1000,1\le m\le 3000$

解题思路

此题可以用诸多算法来解决，如最短路算法，等。这里主要是介绍如何使用$bfs$过这题。
其实用$bfs$也非常简单，就是从每一个节点开始按路径扩展，这里不再多讲。

注意这里的图是单向图，只用建立一条边就可以了。

---

最后，祝大家早日

上代码

#include<bits/stdc++.h>using namespace std;vector<int>     road[200010];
queue<int>      q;
bool            vis[200010];
int             bfs[200010];
int             base[200010];
int             n,pos;inline bool pd(int x,int y)
{return base[x]<base[y];
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(int i=1; i<n; i++){int x,y;cin>>x>>y;road[x].push_back(y);road[y].push_back(x);}for(int i=1; i<=n; i++){int x;cin>>x;base[x]=i;}for(int i=1; i<=n; i++)sort(&road[i][0],&road[i][road[i].size()],pd);q.push(1);vis[1]=true;while(q.size()){int now=q.front();q.pop();bfs[now]=++pos;for(int i=0; i<road[now].size(); i++){if(!vis[road[now][i]]){vis[road[now][i]]=true;q.push(road[now][i]);}}}for(int i=1; i<=n; i++){if(bfs[i]!=base[i]){cout<<"No"<<endl;return 0;}}cout<<"Yes"<<endl;return 0;
}

完美切题$\sim$

这篇关于51nod 2600 小Biu的旅行的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---