P1346 电车网页链接P1346 电车题目描述在一个神奇的小镇上有着一个特别的电车网络它由一些路口和轨道组成每个路口都连接着若干个轨道每个轨道都通向一个路口不排除有的观光轨道转一圈后返回路口的可能。在每个路口都有一个开关决定着出去的轨道每个开关都有一个默认的状态每辆电车行驶到路口之后只能从开关所指向的轨道出去如果电车司机想走另一个轨道他就必须下车切换开关的状态。为了行驶向目标地点电车司机不得不经常下车来切换开关于是他们想请你写一个程序计算一辆电车从路口A AA到路口B BB司机最少需要下车切换几次开关。输入格式第一行有3 33个整数N , A , B N,A,BN,A,B2 ≤ 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输入 #13 2 1 2 2 3 2 3 1 2 1 2输出 #10解题思路本题是有向图最短路建模问题核心是将开关切换次数转化为边权求解起点到终点的最短路径。将每个路口视为图的节点每条出站轨道视为有向边开关默认指向的第一条轨道无需切换对应边权为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表示不可达否则输出最短切换次数。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll maxn10010;constll inf1e8;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 i1;in;i)for(ll j1;jn;j){g[i][j]inf;g[i][i]0;}for(ll i1;in;i){scanf(%lld,k);for(ll j1;jk;j){ll a;scanf(%lld,a);if(j1)g[i][a]0;elseg[i][a]1;}}for(ll k1;kn;k)for(ll i1;in;i)for(ll j1;jn;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;}