P1346 电车：DFS 与 Dijkstra 算法实现

题目描述

第一行有 3 个整数 N, A, B（2 ≤ N ≤ 100, 1 ≤ A, B ≤ N），分别表示路口的数量，以及电车的起点和终点。

接下来有 N 行，每行的开头有一个数字 Ki（0 ≤ Ki ≤ N-1），表示这个路口与 Ki 条轨道相连。接下来有 Ki 个数字表示每条轨道所通向的路口，开关默认指向第一个数字表示的轨道。

输出文件只有一个数字，表示从 A 到 B 所需的最少的切换开关次数，若无法从 A 前往 B，输出 -1。

解题方案

方法一：DFS

由于数据范围较小，可以使用暴力搜索解决。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int k[150][150], kk[150];
int n, a, b, mi = 0x3f3f3f3f, f = 0;

void dfs(int j, int ans) {
    if (kk[j] != 0 && ans + 1 >= kk[j]) return;
    kk[j] = ans + 1;
    for (int i = 1; k[j][i] != 0; i++) {
        if (k[j][i] == b) {
            mi = min(mi, ans);
            f = 1;
            break;
        }
        dfs(k[j][i], ans);
        if (i == 1) ans += 1;
    }
}

signed main() {
    cin >> n >> a >> b;
     ki;
     ( j = ; j <= n; j++) {
        cin >> ki;
         ( i = ; i <= ki; i++) cin >> k[j][i];
    }
    (a, );
     (f) cout << mi;
     cout << ;
}