因为每条边的权重都为 $1$ ,因此此题退化成了 AcWing 847. 图中点的层次
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 405, INF = 0x3f3f3f3f;
int f[N][N], g[N][N];//f 铁路 g 公路
int d[N];
int n, m;
int bfs(int g[][N])
{
memset(d, -1, sizeof d);
d[1] = 0;
queue<int> que;
que.push(1);
while(!que.empty())
{
int v = que.front();
que.pop();
for(int i = 1; i <= n; i++)
{
if(g[v][i] == 1)
{
if(d[i] != -1) continue;
d[i] = d[v] + 1;
que.push(i);
}
}
}
return d[n];
}
int main()
{
cin >> n >> m;
//初始化,因为只输入铁路,且任意两个城市没有铁路就一定有公路
//因此默认铁路无边,公路有边
memset(f, 0x3f, sizeof f);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
g[i][j] = 1;
while(m--)
{
int a, b;
cin >> a >> b;
f[a][b] = f[b][a] = 1;
g[a][b] = g[b][a] = INF;
}
if(f[1][n] == 1) cout << bfs(g);
else cout << bfs(f);
return 0;
}