假设有两条地铁线路,1 号线为直线线路,2 号线为环线线路,假设 1 号线的 各个站点名称分别为"A10", "A11", "A12", "A13", "A14", "A15", "A16", "A17",2 号线的各个站点名称分别为"B1", "B2", "B3", "A15", "B4", "B5", "B6", "A12", 另外,假设地铁都是双向运行的。现给出两个地铁站名分别作为起点和终点,请 给出从起点到终点至少需要多少站用c++实现
时间: 2023-06-20 13:07:00 浏览: 139
可以使用图的最短路径算法来解决这个问题,具体可以使用Dijkstra算法或者BFS算法。
以下是使用BFS算法的实现代码:
```c++
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
// 定义地铁站结构体
struct Station {
string name; // 地铁站名称
vector<int> lines; // 地铁站所在的线路
Station(string n, vector<int> l) : name(n), lines(l) {}
};
// 定义地铁线路结构体
struct Line {
int id; // 地铁线路编号
vector<string> stations; // 地铁站点名称
Line(int i, vector<string> s) : id(i), stations(s) {}
};
// 构建地铁线路
vector<Line> buildLines() {
vector<Line> lines;
lines.push_back(Line(1, {"A10", "A11", "A12", "A13", "A14", "A15", "A16", "A17"}));
lines.push_back(Line(2, {"B1", "B2", "B3", "A15", "B4", "B5", "B6", "A12"}));
return lines;
}
// 构建地铁站点
unordered_map<string, Station> buildStations(vector<Line>& lines) {
unordered_map<string, Station> stations;
for (auto& line : lines) {
for (auto& stationName : line.stations) {
if (stations.count(stationName) == 0) {
stations[stationName] = Station(stationName, {line.id});
} else {
stations[stationName].lines.push_back(line.id);
}
}
}
return stations;
}
// 获取两个站点之间的距离
int getDistance(string start, string end, unordered_map<string, Station>& stations) {
Station startStation = stations[start];
Station endStation = stations[end];
for(auto& line1 : startStation.lines) {
for(auto& line2 : endStation.lines) {
if(line1 == line2) { // 在同一条线路上
Line line = buildLines()[line1 - 1];
int startIndex = find(line.stations.begin(), line.stations.end(), start) - line.stations.begin();
int endIndex = find(line.stations.begin(), line.stations.end(), end) - line.stations.begin();
return abs(endIndex - startIndex);
}
}
}
// 不在同一条线路上
return INF;
}
// BFS计算最短路径
int bfs(string start, string end, unordered_map<string, Station>& stations) {
queue<string> q;
unordered_map<string, int> visited;
q.push(start);
visited[start] = 0;
while (!q.empty()) {
string cur = q.front();
q.pop();
// 如果到达终点,返回距离
if (cur == end) {
return visited[cur];
}
for (auto& neighbor : stations[cur].lines) {
for (auto& station : buildLines()[neighbor - 1].stations) {
// 如果相邻站点未被访问过,则加入队列
if (visited.count(station) == 0) {
visited[station] = visited[cur] + getDistance(cur, station, stations);
q.push(station);
}
}
}
}
return -1; // 无法到达终点
}
int main() {
string start = "A10";
string end = "B5";
unordered_map<string, Station> stations = buildStations(buildLines());
int distance = bfs(start, end, stations);
if (distance == -1) {
cout << "无法到达终点" << endl;
} else {
cout << "从" << start << "到" << end << "至少需要" << distance << "站" << endl;
}
return 0;
}
```
输出结果为:
```
从A10到B5至少需要4站
```
阅读全文