信息学奥赛一本通 1377：最优乘车(travel) | 洛谷 P5767 [NOI1997] 最优乘车

【题目链接】

ybt 1377最优乘车(travel)
洛谷 P5767 [NOI1997] 最优乘车

注意每行末尾的换行符可能是"\r\n"或"\n"。

【题目考点】

1. 图论最短路径

• 无权图求最短路径方法广搜
• 带权图求最短路径方法FloydDijkstraSPFA等

【解题思路】

首先建模。题目要求的是换乘次数的最小值因此尝试把边和换乘的概念联系在一起。
该题中的巴士是“单程巴士”因此该图是有向无权图。该问题中的“最短路径”指的是有向无权图中的最短路径即两点之间路径上边的条数。以巴士站为顶点如果两顶点之间有边说明两巴士站之间有直达的巴士线路。
如果两顶点之间最短路径长度为1那么换乘次数是0。
如果两顶点之间最短路径长度为2那么换乘次数是1。
…
如果两顶点之间最短路径长度为x那么换乘次数是x-1。

输入时一条线路上任何两顶点之间都要从前面的顶点向后面的顶点连一条有向边。

解法1广搜

使用广搜可以求无权图上的最短路径问题复杂度不超过为$O(V^2)$。
用广搜求顶点1到顶点n的最短路径

• 如果存在则输出最短路径长度减1
• 如果不存在输出NO

解法2把无权图当做带权图求最短路径

对于无权图可以将该图每条边的权值都视为1而后就可以使用FloydDijkstraSPFA等方法求解。
本题解只展示Floyd算法其他算法不再赘述。

【注意】由于每行末尾可能是"\r\n"因此在输入第一行m与n后需要去掉本行的换行符时不能只写一句cin.get()或getchar()因为当结尾是"\r\n"时只会读入"\r"还留下了"\n"。
这里可以使用getline(cin, s)读入整行一直读完本行的’\n’或写if(cin.get() == '\r')cin.get();。

【题解代码】

解法1广搜

#include<bits/stdc++.h>
using namespace std;
#define N 505
struct Node
{
	int v, d;//v顶点 d到起始点的距离 
	Node(){}
	Node(int a, int b):v(a), d(b){}
};
bool vis[N];//vis[i]顶点i是否已访问过 
int n, edge[N][N];//n顶点数 edge邻接矩阵 
int bfs()//返回值顶点1到顶点n的最短路径长度如果找不到返回-1。 
{
	queue<Node> que;
	vis[1] = true;
	que.push(Node(1, 0));
	while(que.empty() == false)
	{
		int u = que.front().v, d = que.front().d;
		que.pop();
		if(u == n)//找到解 
			return d;
		for(int i = 1; i <= n; ++i)
		{
			if(edge[u][i] && vis[i] == false)
			{
				vis[i] = true;
				que.push(Node(i, d+1));
			}
		}
	}
	return -1;
} 
int main()
{
	string s;
	int a, m;//m:巴士线路数量 
	cin >> m >> n;
	getline(cin, s);//读掉末尾的换行符注意不能用cin.get()因为末尾可能是"\r\n" 
	for(int k = 1; k <= m; ++k)
	{
		vector<int> vec; 
		getline(cin, s);
		stringstream ss(s);
		while(ss >> a)
			vec.push_back(a);
		for(int i = 0; i < vec.size()-1; ++i)//枚举vec中的所有数对 
			for(int j = i+1; j < vec.size(); ++j)
				edge[vec[i]][vec[j]] = 1;//为每个数对都建单向边 
	}
	int len = bfs();//最短路径长度
	if(len == -1)//没有找到最短路径 
		cout << "NO"; 
	else 
		cout << len-1;//换车次数是路径长度减一 
	return 0;
}

解法2把无权图当做带权图求最短路径

• Floyd算法

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 505
bool vis[N];//vis[i]顶点i是否已访问过 
int n, edge[N][N], dis[N][N];//n顶点数 edge邻接矩阵 
void floyd()
{
	memset(dis, 0x3f, sizeof(dis));
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
		{
			if(i == j)
				dis[i][j] = 0;
			if(edge[i][j])
				dis[i][j] = edge[i][j];
		}
	for(int k = 1; k <= n; ++k)
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n; ++j)
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
int main()
{
	string s;
	int a, m;//m:巴士线路数量 
	cin >> m >> n;
	getline(cin, s);//读掉末尾的换行符注意不能用cin.get()因为末尾可能是"\r\n" 
	for(int k = 1; k <= m; ++k)
	{
		vector<int> vec; 
		getline(cin, s);
		stringstream ss(s);
		while(ss >> a)
			vec.push_back(a);
		for(int i = 0; i < vec.size()-1; ++i)//枚举vec中的所有数对 
			for(int j = i+1; j < vec.size(); ++j)
				edge[vec[i]][vec[j]] = 1;//为每个数对都建单向边 
	}
	floyd();
	if(dis[1][n] == INF)//没有找到最短路径 
		cout << "NO"; 
	else 
		cout << dis[1][n]-1;//换车次数是路径长度减一 
	return 0;
}