P1346 电车
网页链接
P1346 电车
题目描述
在一个神奇的小镇上有着一个特别的电车网络，它由一些路口和轨道组成，每个路口都连接着若干个轨道，每个轨道都通向一个路口（不排除有的观光轨道转一圈后返回路口的可能）。在每个路口，都有一个开关决定着出去的轨道，每个开关都有一个默认的状态，每辆电车行驶到路口之后，只能从开关所指向的轨道出去，如果电车司机想走另一个轨道，他就必须下车切换开关的状态。
为了行驶向目标地点，电车司机不得不经常下车来切换开关，于是，他们想请你写一个程序，计算一辆电车从路口A AA到路口B BB，司机最少需要下车切换几次开关。
输入格式
第一行有3 33个整数N , A , B N,A,BN,A,B（2 ≤ N ≤ 100 , 1 ≤ A , B ≤ N 2 \leq N \leq 100, 1 \leq A,B \leq N2≤N≤100,1≤A,B≤N），分别表示路口的数量，和电车的起点，终点。
接下来有N NN行，每行的开头有一个数字K i K_iKi（0 ≤ K i ≤ N − 1 0 \leq K_i \leq N-10≤Ki≤N−1），表示这个路口与K i K_iKi条轨道相连，接下来有K i K_iKi个数字表示每条轨道所通向的路口，开关默认指向第一个数字表示的轨道。
输出格式
输出文件只有一个数字，表示从A AA到B BB所需的最少的切换开关次数，若无法从A AA前往B BB，输出− 1 -1−1。
输入输出样例 #1
输入 #1
3 2 1 2 2 3 2 3 1 2 1 2输出 #1
0解题思路
本题是有向图最短路建模问题，核心是将开关切换次数转化为边权，求解起点到终点的最短路径。
将每个路口视为图的节点，每条出站轨道视为有向边：开关默认指向的第一条轨道无需切换，对应边权为0；选择其余轨道需要切换一次开关，对应边权为1。此时从起点A到终点B的最短路径长度，就是最少需要下车切换开关的次数。
由于节点数量N ≤ 100 N \le 100N≤100，数据规模极小，采用Floyd 算法求解全源最短路，代码实现简洁直观。初始化邻接矩阵为无穷大，对角线置0；按输入规则构建有向带权图；通过三重循环枚举中间节点，更新所有节点对的最短路径。最终若起点到终点距离仍为无穷大，说明不可达，输出-1；否则输出最短距离。算法时间复杂度O ( N 3 ) O(N^3)O(N3)，完全适配题目数据约束。
总结
核心逻辑：把开关切换次数抽象为边权，将实际问题转化为有向图最短路，利用 Floyd 算法高效求解。
关键操作：邻接矩阵初始化、按轨道顺序赋予边权、三重循环执行路径松弛、判断可达性并输出结果。
效率保障：节点数量少，立方级复杂度无运行压力，代码简洁不易出错。
代码简要说明
- 矩阵初始化：邻接矩阵
g初始化为极大值inf，对角线元素g[i][i]置0，表示节点到自身无需切换开关。 - 构建带权图：遍历每个路口的所有出站轨道；第一条轨道边权设为0（默认方向，无需切换），其余轨道边权设为1（需要切换一次）。
- Floyd 算法：三重循环结构，外层枚举中转节点
k，内层枚举起点i和终点j，用g[i][k] + g[k][j]更新g[i][j]的最小值。 - 结果输出：判断起点到终点的距离是否仍为无穷大，是则输出
-1表示不可达，否则输出最短切换次数。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll maxn=100+10;constll inf=1e+8;ll g[maxn][maxn];ll n,m,k,f,t;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%lld%lld%lld",&n,&f,&t);for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++){g[i][j]=inf;g[i][i]=0;}for(ll i=1;i<=n;i++){scanf("%lld",&k);for(ll j=1;j<=k;j++){ll a;scanf("%lld",&a);if(j==1)g[i][a]=0;elseg[i][a]=1;}}for(ll k=1;k<=n;k++)for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)g[i][j]=min(g[i][j],g[i][k]+g[k][j]);if(g[f][t]==inf)puts("-1");elseprintf("%lld",g[f][t]);return0;}
