起点到终点需要倒车几次
给定n个点,m条公交路线,求1点到n点需要倒车几次(即乘坐几次公交车)。
对于每条公交路线,对于每个车站而言,该车站前面所有的站牌到该点站牌连一条边距离为1。
这样,求1点到n点的最短距离即可,因为每条边的距离为1,所以最终答案是起点到终点距离 - 1
。
因为距离为1,所以可以用bfs来做。
时间复杂度$O(M*N^2)$,空间复杂度$O(N^2)$,时间复杂度主要是建图时候比较高,邻接矩阵实现。
AC代码
#include <iostream>
#include <cstring>
#include <sstream>
#include <queue>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dis[N];
int stop[N];
void bfs(){
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
queue<int> q;
q.push(1);
while (q.size()){
auto t = q.front();
q.pop();
for (int i = 1 ; i <= n ; i ++){
if (g[t][i] > 0 && dis[i] == INF) {
dis[i] = dis[t] + 1;
q.push(i);
}
}
}
}
int main(){
cin >> m >> n;
getchar();
//读入m条路线
for (int i = 0 ; i < m ; i ++){
string line;
getline(cin, line);
stringstream ssin(line);
int cnt = 0, t;
while (ssin >> t) stop[cnt++] = t;
//每个点到后面点连一条距离为1的边
for (int j = 0 ; j < cnt ; j ++){
for (int k = j + 1 ; k < cnt ;k ++){
g[stop[j]][stop[k]] = 1;
}
}
}
//求1点到n点的最短距离
bfs();
//输出结果
if (dis[n] == INF) cout << "NO";
else cout << max(dis[n] - 1, 0);
return 0;
}