bfs + 邻接矩阵

#include <iostream>  //scanf, cin, cout, freopen, fclose
#include <queue>     //queue
using namespace std;

int m;     // m个物品转换配方
int x, y;  // 求从 物品x 变为 物品y 的最小魔法次数

bool g[110][110];  // 邻接矩阵
bool vis[10010];   // 标记数组

// 节点
struct Node {
  int pos;    // 位置(position)
  int steps;  // 步数
};

/// @brief 广度优先搜索函数（记住模板很重要啊！！！）
/// @return 步数（无法到达则为-1）
int bfs() {
  // 为bfs做准备
  queue<Node> q;  // bfs队列
  q.push({x, 0});
  vis[x] = true;  // 标记起点，防止a->b, b->a, a->b…… 之类的情况

  // bfs
  while (q.size() /*q.size() 或 !q.empty()都代表队列不为空*/) {
    Node n1 = q.front();
    q.pop();

    if (n1.pos == y) return n1.steps;  // 如果搜索到终点则返回步数

    for (int i = 0; i < 100; ++i) {
      if (g[n1.pos][i] /*表示存在从 n1.pos 到 i 的物品转换配方*/ &&
          !vis[i] /*未被标记*/) {
        vis[i] = true;  // 标记
        q.push({i, n1.steps + 1});
      }
    }
  }
  // 从while循环中出来表示找不到从 物品x 到 物品y 的方案
  return -1;
}

int main() {
  //freopen("magic.in", "r", stdin);
  //freopen("magic.out", "w", stdout);

  /*
    int n;
    cin >> n >> m;
  */
  scanf("%*d %d", &m);  //%*d表示不存到变量里
  // 建图
  for (int i = 0; i < m; ++i) {
    int a, b;  // 可以从a变为b
    cin >> a >> b;
    g[a][b] = true;
  }
  cin >> x >> y;  // 求从 物品x 变为 物品y 的最小魔法次数
  cout << bfs();

  //fclose(stdin);
  //fclose(stdout);
  return 0;
}