网站开发话题,seo 重庆,wordpress 搭配keycdn,前端最难学的是哪部分电车
luogu 1346
题目大意#xff1a;
有n个点#xff0c;要从一个点到另一个点#xff0c;每个点连接着其他ai个点#xff0c;到连接的第一个点路径长度为0#xff0c;其他长度为1#xff0c;求最短路
题目描述
在一个神奇的小镇上有着一个特别的电车网络#xff…电车
luogu 1346
题目大意
有n个点要从一个点到另一个点每个点连接着其他ai个点到连接的第一个点路径长度为0其他长度为1求最短路
题目描述
在一个神奇的小镇上有着一个特别的电车网络它由一些路口和轨道组成每个路口都连接着若干个轨道每个轨道都通向一个路口不排除有的观光轨道转一圈后返回路口的可能。在每个路口都有一个开关决定着出去的轨道每个开关都有一个默认的状态每辆电车行驶到路口之后只能从开关所指向的轨道出去如果电车司机想走另一个轨道他就必须下车切换开关的状态。 为了行驶向目标地点电车司机不得不经常下车来切换开关于是他们想请你写一个程序计算一辆从路口A到路口B最少需要下车切换几次开关。
输入输出格式
输入格式
第一行有3个整数2N1001ABN分别表示路口的数量和电车的起点终点。 接下来有N行每行的开头有一个数字Ki(0KiN-1)表示这个路口与Ki条轨道相连接下来有Ki个数字表示每条轨道所通向的路口开关默认指向第一个数字表示的轨道。
输出格式
输出文件只有一个数字表示从A到B所需的最少的切换开关次数若无法从A前往B输出-1。
输入输出样例
输入样例#1
3 2 1
2 2 3
2 3 1
2 1 2输出样例#1
0解题思路
直接用邻接矩阵存每一次把连接的第一个点和其他点分开处理在特判一下就可以了
代码
#includecstdio
#includecstring
#includeiostream
#includequeue
using namespace std;
int n,a1,b1,now,q,b[105],p[105],a[105][105];
int main()
{scanf(%d %d %d,n,a1,b1);for (int i1;in;i){scanf(%d,a[i][0]);//个数for (int j1;ja[i][0];j)scanf(%d,a[i][j]);}memset(b,127/3,sizeof(b));//预处理qb[1];//记下来b[a1]0;//初值p[a1]1;//记录queueintd;d.push(a1);while(!d.empty()){nowd.front();//取出来d.pop(); if (now)//是否有相连的点{if (b[now]b[a[now][1]])//更优{b[a[now][1]]b[now];//代替if (!p[a[now][1]])//不在队列{p[a[now][1]]1;//记录d.push(a[now][1]);//入队}}}for (int i2;ia[now][0];i)if (b[now]1b[a[now][i]])//加一{b[a[now][i]]b[now]1;//同上if (!p[a[now][i]]){p[a[now][i]]1;d.push(a[now][i]);}}p[now]0;//清零} if (b[b1]q) printf(-1);//特判else printf(%d,b[b1]);
}
