AcWing 920. 最优乘车 题解（最短路—BFS）

AcWing 920. 最优乘车
因为边权重都是1，所以可以直接用bfs求最短路，本题有一个迷惑的地方在代码中已做解释，这种思维转换方式可以好好体会以下

#include

using namespace std;

const int N = 510;

int n,  m;
int d[N];
bool g[N][N];
int stop[N];
int q[N];

void bfs(){
	memset(d, 0x3f, sizeof d);  //初始化距离 
	q[0] = 1;
	d[1] = 0;
	int hh = 0, tt = 0;
	
	while(hh <= tt){
		int t = q[hh ++ ];
		for(int i = 1; i <= n; i ++ ){
			//之前我一直在迷惑为什么1~n的换乘次数会等于1~n的乘车次数-1
			//其实道理很简单，即从x~y点的最近距离要么是1，要么是换乘次数最少的距离
			//如果x、y在同一条线路，那最短距离肯定是1
			//如果不在同一条线路，那最短距离就会被换乘的站点之间更新，因为一直在找最小距离
			//所以1~n的换乘次数会等于1~n的乘车次数-1
			if(d[i] > d[t] + 1 && g[t][i]){  //如果点i和点t之间有通路且通过t可以找到到达i的更小距离 
				d[i] = d[t] + 1;
				q[ ++ tt] = i; 
			}
		}
	}
}

int main()
{
	cin>>m>>n;
	string line;
	getline(cin, line);  //读取m、n后面的空格/换行符
	while(m -- ){
		getline(cin, line);  //读入一行
		stringstream ssin(line);  //定义字符串流ssin，用line初始化ssin（相当于赋值） 
		int cnt = 0, p;
		while(ssin>>p) stop[cnt ++ ] = p;
		//将同一条线路的每个站点和之后的每个站点连一条线 
		for(int i = 0; i < cnt; i ++ ){
			for(int j = i + 1; j < cnt; j ++ ){
				g[stop[i]][stop[j]] = true;
			}
		}
	}
	bfs();
	
	if(d[n] == 0x3f3f3f3f) cout<<"NO"<