AcWing 920. 最优乘车 BFS DIJKSTRA SPFA 方法
标签：cto current using 顺序 nbsp 商业 ref win memory
地址 https://www.acwing.com/problem/content/description/922/
H城是一个旅游胜地，每年都有成千上万的人前来观光。
为方便游客，
巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。
每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。
一名旅客最近到H城旅游，他很想去S公园游玩，
但如果从他所在的饭店没有一路巴士可以直接到达S公园，
则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士,
这样换乘几次后到达S公园。
现在用整数1,2,…N 给H城的所有的巴士站编号，
约定这名旅客所在饭店的巴士站编号为1，S公园巴士站的编号为N。
写一个程序，帮助这名旅客寻找一个最优乘车方案,
使他在从饭店乘车到S公园的过程中换乘的次数最少。
输入格式
第一行有两个数字M和N，表示开通了M条单程巴士线路，总共有N个车站。
从第二行到第M+1行依次给出了第1条到第M条巴士线路的信息，
其中第i+1行给出的是第i条巴士线路的信息，
从左至右按运行顺序依次给出了该线路上的所有站号，
相邻两个站号之间用一个空格隔开。
输出格式
共一行，如果无法乘巴士从饭店到达S公园，则输出”NO”，
否则输出最少换乘次数，换乘次数为0表示不需换车即可到达。
数据范围
1≤M≤100,
1≤N≤500
输入样例：
3 7
6 7
4 7 3 6
2 1 3 5
输出样例：
2
算法1
BFS
建图 每个车站到达后面的车站的距离都是1
那么1到达n的最短距离就是转车次数+1
比如例题中
1到2 3 5 都是距离1
2到 1 3 5 都是距离1
1先到3 3再到7 就是1到7的最短距离
C++ 代码
#include
#include
#include using namespace std;
const int N = 510;
int n, m;
int stop[N];
/*
3 7
6 7
4 7 3 6
2 1 3 5
输出样例：
2
*/
int g[N][N];
int bfs()
{
queueint,int>> q;
for (int i = 1; i ) {
if (g[1][i] != 0) {
q.push({ i,0 });
g[1][i] = 0;
}
}
while (q.size()) {
int currentStop = q.front().first;
int step = q.front().second;
q.pop();
if (currentStop == n) return step;
for (int i = 1; i ) {
if (g[currentStop][i] != 0) {
q.push({ i ,step+1});
g[currentStop][i] = 0;
}
}
}
return -1;
}
int main()
{
cin >> m >> n;
string line;
getline(cin, line);
while (m--) {
getline(cin, line);
stringstream ssin(line);
int cnt = 0, p;
while (ssin >> p) stop[cnt++] = p;
//每个汽车的前站达到后站的距离都为1 因为是同一辆车 未换车
for (int i = 0; i ) {
for (int j = i + 1; j ) {
g[stop[i]][stop[j]] = 1;
}
}
}
int ret = bfs();
if(-1==ret) cout "NO" endl;
else cout endl;
return 0;
}
作者：itdef
链接：https://www.acwing.com/solution/content/15468/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
View Code
算法2
dijkstra
#include
#include
#include
#include using namespace std;
const int N = 510;
int n, m;
int stop[N];
/*
3 7
6 7
4 7 3 6
2 1 3 5
输出样例：
2
*/
int g[N][N];
int dist[N];
bool st[N];
int dij()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i 1; i++) {
int t = -1;
for (int j = 1; j ) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
for (int j = 1; j ) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
st[t] = true;
}
return dist[n];
}
int main()
{
cin >> m >> n;
memset(g, 0x3f, sizeof g);
string line;
getline(cin, line);
while (m--) {
getline(cin, line);
stringstream ssin(line);
int cnt = 0, p;
while (ssin >> p) stop[cnt++] = p;
//每个汽车的前站达到后站的距离都为1 因为是同一辆车 未换车
for (int i = 0; i ) {
for (int j = i + 1; j ) {
g[stop[i]][stop[j]] = 1;
}
}
}
int ret = dij();
if ( ret > 0x3f3f3f3f/2) cout "NO" endl;
else cout 1 endl;
return 0;
}
作者：itdef
链接：https://www.acwing.com/solution/content/15468/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
View Code
算法3
spfa
C++ 代码
#include
#include
#include
#include
#include using namespace std;
const int N = 510;
int n, m;
int stop[N];
/*
3 7
6 7
4 7 3 6
2 1 3 5
输出样例：
2
*/
vectorint, int>> g[N];
int dist[N];
bool st[N];
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queueint> q;
q.push(1);
st[1] = true;
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = 0; i ) {
int j = g[t][i].first;
int w = g[t][i].second;
if (dist[j] > dist[t] + w) {
dist[j] = dist[t] + w;
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main()
{
cin >> m >> n;
string line;
getline(cin, line);
while (m--) {
getline(cin, line);
stringstream ssin(line);
int cnt = 0, p;
while (ssin >> p) stop[cnt++] = p;
//每个汽车的前站达到后站的距离都为1 因为是同一辆车 未换车
for (int i = 0; i ) {
for (int j = i + 1; j ) {
g[stop[i]].push_back({ stop[j],1 });
}
}
}
int ret = spfa();
if (ret == 0x3f3f3f3f) cout "NO" endl;
else cout 1 endl;
return 0;
}
作者：itdef
链接：https://www.acwing.com/solution/content/15468/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
View Code
AcWing 920. 最优乘车 BFS DIJKSTRA SPFA 方法
标签：cto current using 顺序 nbsp 商业 ref win memory
原文地址：https://www.cnblogs.com/itdef/p/13210396.html
评论