数据结构课程设计

交通查询系统设计

[问题描述]

今天铁路交通网络非常发达，人们在出差、旅游时，不仅关注交通费用，还关注里程和时间。请按照下图设计一个交通查询系统，能够满足旅客查询从任一个城市到另一个城市的最短里程、最低花费、最短时间、最少中转次数等问题。

[基本要求]

设计合适的数据结构和算法编写程序完成上述功能，并具有查询界面，能够按照下拉菜单选项进行选择查询。

Dijkstra写法:

// 交通图的一些信息
// 城市
/*
北京(1)西安(2)郑州(3)徐州(4)成都(5)广州(6)上海(7)
*/
//顶点个数,边的个数,顶点信息
/*
7 10
1 2 3 4 5 6 7
*/
//交通图的距离公里数的数据
/*
0    2553  695   704   9999  9999  9999
2553 0     511   9999  812   9999  9999
695  511   0     349   9999  1579  651
704  9999  349   0     9999  9999  349
9999 812   9999  9999  0     2368  9999
9999 9999  1579  9999  2368  0     1385
9999 9999  651   349   9999  1385  0
*/
//交通图的时间的数据
/*
0    8     2.3   2.5   9999  9999  9999
8    0     1.5   9999  3     9999  9999
2.3  1.5   0     1.2   9999  5     2
2.5  9999  1.2   0     9999  9999  1.2
9999 3     9999  9999  0     7     9999
9999 9999  5     9999  7     0     4
9999 9999  2     1.2   9999  4     0
*/
// 交通图的费用的数据
/*
0    885   202   225   9999  9999  9999
885  0     148   9999  283   9999  9999
202  148   0     112   9999  495   162
225  9999  112   0     9999  9999  112
9999 283   9999  9999  0     684   9999
9999 9999  495   9999  684   0     386
9999 9999  162   112   9999  386   0
*/

#include <iostream>
#include <climits>
#include<string>
#include <cstdlib> 
#include <algorithm>

#define max_vexs 7 // 顶点的最大个数
#define max_number 9999 // 代表无穷大

using namespace std;

bool visted[max_vexs]; // 代表这个顶点是否被访问过
int path[max_vexs]; // 代表这个顶点的路径
double power[max_vexs]; // 代表这个顶点的权值

const int vexsnumber = 7;
const int arcsnumber = 10;
const int vexs[max_vexs] = { 1, 2, 3, 4, 5, 6, 7 };
const string city[max_vexs] = { "北京","西安","郑州","徐州","成都","广州","上海" }; // 顶点的信息
const double arcs[max_vexs][max_vexs] = {
    {0, 2553, 695, 704, max_number, max_number, max_number},
    {2553, 0, 511, max_number, 812, max_number, max_number},
    {695, 511, 0, 349, max_number, 1579, 651},
    {704, max_number, 349, 0, max_number, max_number, 349},
    {max_number, 812, max_number, max_number, 0, 2368, max_number},
    {max_number, max_number, 1579, max_number, 2368, 0, 1385},
    {max_number, max_number, 651, 349, max_number, 1385, 0}
};
const double Time[max_vexs][max_vexs] = {
    {0, 8, 2.3, 2.5, max_number, max_number, max_number},
    {8, 0, 1.5, max_number, 3, max_number, max_number},
    {2.3, 1.5, 0, 1.2, max_number, 5, 2},
    {2.5, max_number, 1.2, 0, max_number, max_number, 1.2},
    {max_number, 3, max_number, max_number, 0, 7, max_number},
    {max_number, max_number, 5, max_number, 7, 0, 4},
    {max_number, max_number, 2, 1.2, max_number, 4, 0}
};
const double cost[max_vexs][max_vexs] = {
    {0, 885, 202, 225, max_number, max_number, max_number},
    {885, 0, 148, max_number, 283, max_number, max_number},
    {202, 148, 0, 112, max_number, 495, 162},
    {225, max_number, 112, 0, max_number, max_number, 112},
    {max_number, 283, max_number, max_number, 0, 684, max_number},
    {max_number, max_number, 495, max_number, 684, 0, 386},
    {max_number, max_number, 162, 112, max_number, 386, 0}
};

struct position {
    int x, y;
};
struct node {
    position data;
    struct node* next;
};
class queue { // 队列
private:
    node* root;
public:
    queue() {
        root = new node;
        root->next = NULL;
    }
    void push(position data) {
        node* node1 = root;
        while (node1->next) {
            node1 = node1->next;
        }
        node* node2 = new node;
        node2->data = data;
        node2->next = nullptr;
        node1->next = node2;
    }
    position front() {
        if (root->next == NULL) {
            return { -1,-1 };
        }
        else {
            position number = root->next->data;
            return number;
        }
    };
    bool empty() {
        return root->next == NULL;
    }
    void pop() {
        if (root->next == NULL) return;
        node* node1 = root->next;
        root->next = node1->next;
        delete node1;
    }
    ~queue() {
        while (root) {
            node* temp = root;
            root = root->next;
            delete temp;
        }
    }
};

typedef struct Graph {
    char vexs[max_vexs]; // 顶点的信息
    double arcs[max_vexs][max_vexs]; // 代表这个图的边的信息
    double time[max_vexs][max_vexs]; // 代表这个图的边的时间
    double cost[max_vexs][max_vexs]; // 代表这个图的边的费用
    int vexsnumber; // 顶点的个数
    int arcsnumber; // 边的个数
} Graph;

Graph* InitGraph(int vexs, int arcs) { // 初始化一个图
    Graph* G = new Graph;
    G->vexsnumber = vexs;
    G->arcsnumber = arcs;
    for (int i = 0; i < vexs; i++) {
        for (int j = 0; j < vexs; j++) {
            G->arcs[i][j] = max_number;
            G->time[i][j] = max_number;
            G->cost[i][j] = max_number;
        }
    }
    return G;
}

Graph* CreateGraph() { // 传入一些数据,创建一个图
    Graph* G = InitGraph(vexsnumber, arcsnumber); // 初始化这个图
    for (int i = 0; i < G->vexsnumber; i++) { // 初始化这个图的顶点
        G->vexs[i] = vexs[i];
    }
    for (int i = 0; i < G->vexsnumber; i++) { // 初始化这个图的边
        for (int j = 0; j < G->vexsnumber; j++) {
            G->arcs[i][j] = arcs[i][j];
        }
    }
    for (int i = 0; i < G->vexsnumber; i++) { // 初始化这个图的时间
        for (int j = 0; j < G->vexsnumber; j++) {
            G->time[i][j] = Time[i][j];
        }
    }
    for (int i = 0; i < G->vexsnumber; i++) { // 初始化这个图的费用
        for (int j = 0; j < G->vexsnumber; j++) {
            G->cost[i][j] = cost[i][j];
        }
    }
    return G;
}

void Dijkstra(Graph* G, int start, int end, int type) { // 传入一个图,一个起点,一个终点,一个类型
    for (int i = 0; i < G->vexsnumber; i++) {
        visted[i] = false;
        if (type == 1) {
            power[i] = G->arcs[start][i];
        }
        else if (type == 2) {
            power[i] = G->time[start][i];
        }
        else if (type == 3) {
            power[i] = G->cost[start][i];
        }
        if (power[i] < max_number) {
            path[i] = start;
        }
        else {
            path[i] = -1;
        }
    }
	visted[start] = true;// 起点已经访问
	power[start] = 0; // 起点的权值为0

	for (int k = 1; k < G->vexsnumber; k++) { // 从第二个顶点开始
        float minnumber = max_number;
        int vexs = -1; // 初始化 vexs
        for (int i = 0; i < G->vexsnumber; i++) { 
			if (!visted[i] && power[i] < minnumber) {// 找到未访问的顶点中权值最小的
                minnumber = power[i];
                vexs = i;
            }
        }
        if (vexs == -1) break; // 如果没有找到未访问的顶点，退出循环
		visted[vexs] = true; // 标记为已访问
		for (int j = 0; j < G->vexsnumber; j++) { // 更新权值
			if (!visted[j]) {// 如果这个顶点没有被访问过
				double new_power = power[vexs];// 新的权值
                if (type == 1) {
                    new_power += G->arcs[vexs][j];
                }
                else if (type == 2) {
                    new_power += G->time[vexs][j];
                }
                else if (type == 3) {
                    new_power += G->cost[vexs][j];
                }
				if (new_power < power[j]) { // 如果新的权值小于原来的权值
					power[j] = new_power;// 更新权值
					path[j] = vexs;// 更新路径
                }
            }
        }
    }

    // 打印从start到end的路径和权值
	if (power[end] == max_number) { // 如果终点的权值为无穷大
        cout << "从" << start + 1 << "到" << end + 1 << "没有路径" << endl;
    }
    else {
		if (type == 1) {
            cout << "从 " << city[start] << " 到 " << city[end] << " 的最短距离路径为：";
		}
		else if (type == 2) {
            cout << "从 " << city[start] << " 到 " << city[end] << " 的最短时间路径为：";
		}
		else if (type == 3) {
            cout << "从 " << city[start] << " 到 " << city[end] << " 的最低费用路径为：";
		}
        int route[max_vexs];
        int count = 0;
		for (int v = end; v != start; v = path[v]) { // 从终点开始，一直到起点
			route[count++] = v;// 记录路径
        }
		route[count++] = start;// 记录路径
		for (int i = count - 1; i >= 0; i--) {// 打印路径
            cout << city[route[i]] << "--->";
        }
        cout << "end";
        cout << endl;
		if (type == 1) { // 打印权值
            cout << "总距离为：" << power[end] << " 公里" << endl;
		}
		else if (type == 2) {
            cout << "总时间为：" << power[end] << " 小时" << endl;
		}
		else if (type == 3) {
            cout << "总费用为：" << power[end] << " 元" << endl;
		}
    }
}

void BFS(Graph* G, int start, int end) { // 传入一个图,一个起点,一个终点
    queue q;
	int dist[max_vexs];// 代表从起点到这个顶点的中转次数
	int prev[max_vexs];// 代表这个顶点的前一个顶点
	for (int i = 0; i < G->vexsnumber; i++) {// 初始化
        dist[i] = max_number;
        prev[i] = -1;
    }
    q.push({ start, 0 });
	dist[start] = 0;// 起点的中转次数为0

	while (!q.empty()) { // 广度优先搜索
        position u = q.front();
        q.pop();
		for (int v = 0; v < G->vexsnumber; v++) { // 遍历这个顶点的所有邻接顶点
			if (G->arcs[u.x][v] != max_number && dist[v] == max_number) { // 如果这个顶点没有被访问过
                dist[v] = dist[u.x] + 1;
                prev[v] = u.x;
                q.push({ v, dist[v] });
            }
        }
    }

    // 打印从start到end的路径和中转次数
	if (dist[end] == max_number) {// 如果终点的中转次数为无穷大
        cout << "从" << start + 1 << "到" << end + 1 << "没有路径" << endl;
    }
    else {
        cout << "从 " << city[start] << " 到 " << city[end] << " 的最少中转次数路径为：";
        int route[max_vexs];
        int count = 0;
		for (int v = end; v != start; v = prev[v]) {  // 从终点开始，一直到起点
            route[count++] = v;
        }
        route[count++] = start;
        for (int i = count - 1; i >= 0; i--) {
            cout << city[route[i]] << "--->";
        }
        cout << "end";
        cout << endl;
        cout << "总中转次数为：" << dist[end] - 1 << " 次" << endl;
    }
}

void menu() { // 菜单
    cout << "-------------------------------------------------" << endl;
    cout << "        请选择查询方式:\n";
    cout << "        1. 输入起点与终点进行查询\n";
	cout << "        2. 清空查询记录\n";
    cout << "        0. 退出交通查询系统\n";
    cout << "-------------------------------------------------" << endl;
    Graph* APP = CreateGraph();
    int query_type;
    cout << "---------------------------------------" << endl;
    cout << "     请输入起点与终点进行查询:\n";
    cin >> query_type;
    while (query_type) {
        if (query_type == 2) {
			system("cls"); // 清屏
            menu();
            return;
        }
		if (query_type < 0 || query_type > 4) {
			cout << "输入错误!!!" << endl;
            cout << endl;
            cout << "------------------------------" << endl;
            cout << "     请选择查询方式:\n";
			cin >> query_type;
			continue;
		}
        int start, end;
        cout << "----------------------------------------------------" << endl;
        cout << "(1)北京(2)西安(3)郑州(4)徐州(5)成都(6)广州(7)上海" << endl;
        cout << "----------------------------------------------------" << endl;
        cout << "请选择上面的城市序号:" << endl;
        cout << "终点城市:";
        cin >> start;
        cout << "终点城市:";
		cin >> end;
		if (start < 1 || start > vexsnumber || end < 1 || end > vexsnumber) {
			cout << "输入错误!!!" << endl;
            cout << endl;
			cout << "---------------------------" << endl;
			cout << "     请选择查询方式:\n";
			cin >> query_type;
			continue;
		}
        start--; // 转换为0-based索引
        end--;   // 转换为0-based索引
        switch (query_type) {
        case 1:
            cout << "--------------------------------------------------------------" << endl;
            cout << "最短距离为:" << endl;
            Dijkstra(APP, start, end, 1);
            cout << "最短时间为:" << endl;
            Dijkstra(APP, start, end, 2);
            cout << "最低费用为:" << endl;
            Dijkstra(APP, start, end, 3);
            cout << "最少中转次数查询:" << endl;
            BFS(APP, start, end);
            cout << "--------------------------------------------------------------" << endl;
            break;
        case 0:
            return;
        }
        cout << endl;
        cout << "------------------------------" << endl;
        cout << "     请选择查询方式:\n";
        cin >> query_type;
    }
    delete APP;
}
int main() {
	menu(); // 菜单
    return 0;
}

Floyd写法:

#include <iostream>
#include <climits>
#include <string>
#include <cstdlib>
#include <algorithm>

#define max_vexs 7 // 顶点的最大个数
#define max_number 9999 // 代表无穷大

using namespace std;

const int vexsnumber = 7;
const int arcsnumber = 10;
const int vexs[max_vexs] = { 1, 2, 3, 4, 5, 6, 7 };
const string city[max_vexs] = { "北京","西安","郑州","徐州","成都","广州","上海" }; // 顶点的信息
const double arcs[max_vexs][max_vexs] = {
    {0, 2553, 695, 704, max_number, max_number, max_number},
    {2553, 0, 511, max_number, 812, max_number, max_number},
    {695, 511, 0, 349, max_number, 1579, 651},
    {704, max_number, 349, 0, max_number, max_number, 349},
    {max_number, 812, max_number, max_number, 0, 2368, max_number},
    {max_number, max_number, 1579, max_number, 2368, 0, 1385},
    {max_number, max_number, 651, 349, max_number, 1385, 0}
};
const double Time[max_vexs][max_vexs] = {
    {0, 8, 2.3, 2.5, max_number, max_number, max_number},
    {8, 0, 1.5, max_number, 3, max_number, max_number},
    {2.3, 1.5, 0, 1.2, max_number, 5, 2},
    {2.5, max_number, 1.2, 0, max_number, max_number, 1.2},
    {max_number, 3, max_number, max_number, 0, 7, max_number},
    {max_number, max_number, 5, max_number, 7, 0, 4},
    {max_number, max_number, 2, 1.2, max_number, 4, 0}
};
const double cost[max_vexs][max_vexs] = {
    {0, 885, 202, 225, max_number, max_number, max_number},
    {885, 0, 148, max_number, 283, max_number, max_number},
    {202, 148, 0, 112, max_number, 495, 162},
    {225, max_number, 112, 0, max_number, max_number, 112},
    {max_number, 283, max_number, max_number, 0, 684, max_number},
    {max_number, max_number, 495, max_number, 684, 0, 386},
    {max_number, max_number, 162, 112, max_number, 386, 0}
};

struct position {
    int x, y;
};
struct node {
    position data;
    struct node* next;
};
class queue { // 队列
private:
    node* root;
public:
    queue() {
        root = new node;
        root->next = NULL;
    }
    void push(position data) {
        node* node1 = root;
        while (node1->next) {
            node1 = node1->next;
        }
        node* node2 = new node;
        node2->data = data;
        node2->next = nullptr;
        node1->next = node2;
    }
    position front() {
        if (root->next == NULL) {
            return { -1,-1 };
        }
        else {
            position number = root->next->data;
            return number;
        }
    };
    bool empty() {
        return root->next == NULL;
    }
    void pop() {
        if (root->next == NULL) return;
        node* node1 = root->next;
        root->next = node1->next;
        delete node1;
    }
    ~queue() {
        while (root) {
            node* temp = root;
            root = root->next;
            delete temp;
        }
    }
};

typedef struct Graph {
    char vexs[max_vexs]; // 顶点的信息
    double arcs[max_vexs][max_vexs]; // 代表这个图的边的信息
    double time[max_vexs][max_vexs]; // 代表这个图的边的时间
    double cost[max_vexs][max_vexs]; // 代表这个图的边的费用
    int vexsnumber; // 顶点的个数
    int arcsnumber; // 边的个数
} Graph;

Graph* InitGraph(int vexs, int arcs) { // 初始化一个图
    Graph* G = new Graph;
    G->vexsnumber = vexs;
    G->arcsnumber = arcs;
    for (int i = 0; i < vexs; i++) {
        for (int j = 0; j < vexs; j++) {
            G->arcs[i][j] = max_number;
            G->time[i][j] = max_number;
            G->cost[i][j] = max_number;
        }
    }
    return G;
}

Graph* CreateGraph() { // 传入一些数据,创建一个图
    Graph* G = InitGraph(vexsnumber, arcsnumber); // 初始化这个图
    for (int i = 0; i < G->vexsnumber; i++) { // 初始化这个图的顶点
        G->vexs[i] = vexs[i];
    }
    for (int i = 0; i < G->vexsnumber; i++) { // 初始化这个图的边
        for (int j = 0; j < G->vexsnumber; j++) {
            G->arcs[i][j] = arcs[i][j];
        }
    }
    for (int i = 0; i < G->vexsnumber; i++) { // 初始化这个图的时间
        for (int j = 0; j < G->vexsnumber; j++) {
            G->time[i][j] = Time[i][j];
        }
    }
    for (int i = 0; i < G->vexsnumber; i++) { // 初始化这个图的费用
        for (int j = 0; j < G->vexsnumber; j++) {
            G->cost[i][j] = cost[i][j];
        }
    }
    return G;
}

void Floyd(Graph* G, double dist[max_vexs][max_vexs], int path[max_vexs][max_vexs], double weight[max_vexs][max_vexs]) {
    for (int i = 0; i < G->vexsnumber; i++) {
        for (int j = 0; j < G->vexsnumber; j++) {
            dist[i][j] = weight[i][j];
            if (weight[i][j] < max_number) {
                path[i][j] = i;
            } else {
                path[i][j] = -1;
            }
        }
    }
    for (int k = 0; k < G->vexsnumber; k++) {
        for (int i = 0; i < G->vexsnumber; i++) {
            for (int j = 0; j < G->vexsnumber; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[k][j];
                }
            }
        }
    }
}

void printPath(int path[max_vexs][max_vexs], int start, int end) {
    if (path[start][end] == -1) {
        cout << "没有路径" << endl;
        return;
    }
    int route[max_vexs];
    int count = 0;
    for (int v = end; v != start; v = path[start][v]) {
        route[count++] = v;
    }
    route[count++] = start;
    for (int i = count - 1; i >= 0; i--) {
        cout << city[route[i]] << (i == 0 ? "" : " -> ");
    }
    cout << endl;
}

void BFS(Graph* G, int start, int end) { // 传入一个图,一个起点,一个终点
    queue q;
    int dist[max_vexs];// 代表从起点到这个顶点的中转次数
    int prev[max_vexs];// 代表这个顶点的前一个顶点
    for (int i = 0; i < G->vexsnumber; i++) {// 初始化
        dist[i] = max_number;
        prev[i] = -1;
    }
    q.push({ start, 0 });
    dist[start] = 0;// 起点的中转次数为0
    while (!q.empty()) { // 广度优先搜索
        position u = q.front();
        q.pop();
        for (int v = 0; v < G->vexsnumber; v++) { // 遍历这个顶点的所有邻接顶点
            if (G->arcs[u.x][v] != max_number && dist[v] == max_number) { // 如果这个顶点没有被访问过
                dist[v] = dist[u.x] + 1;
                prev[v] = u.x;
                q.push({ v, dist[v] });
            }
        }
    } // 打印从start到end的路径和中转次数
    if (dist[end] == max_number) {// 如果终点的中转次数为无穷大
        cout << "从" << start + 1 << "到" << end + 1 << "没有路径" << endl;
    }
    else {
        cout << "从 " << city[start] << " 到 " << city[end] << " 的最少中转次数路径为：";
        int route[max_vexs];
        int count = 0;
        for (int v = end; v != start; v = prev[v]) {  // 从终点开始，一直到起点
            route[count++] = v;
        }
        route[count++] = start;
        for (int i = count - 1; i >= 0; i--) {
            cout << city[route[i]] << (i == 0 ? "" : " -> ");
        }
        cout << endl;
        cout << "总中转次数为：" << dist[end] - 1 << " 次" << endl;
    }
}

void menu() { // 菜单
    cout << "-------------------------------------------------" << endl;
    cout << "        请选择查询方式:\n";
    cout << "        1. 输入起点与终点进行查询\n";
    cout << "        2. 清空查询记录\n";
    cout << "        0. 退出交通查询系统\n";
    cout << "-------------------------------------------------" << endl;
    Graph* APP = CreateGraph();
    double dist_length[max_vexs][max_vexs];
    double dist_time[max_vexs][max_vexs];
    double dist_cost[max_vexs][max_vexs];
    int path_length[max_vexs][max_vexs];
    int path_time[max_vexs][max_vexs];
    int path_cost[max_vexs][max_vexs];
    Floyd(APP, dist_length, path_length, APP->arcs);
    Floyd(APP, dist_time, path_time, APP->time);
    Floyd(APP, dist_cost, path_cost, APP->cost);
    int query_type;
    cout << "---------------------------------------" << endl;
    cout << "     请输入起点与终点进行查询:\n";
    cin >> query_type;
    while (query_type) {
        if (query_type == 2) {
            system("cls"); // 清屏
            menu();
            return;
        }
        if (query_type < 0 || query_type > 4) {
            cout << "输入错误!!!" << endl;
            cout << endl;
            cout << "------------------------------" << endl;
            cout << "     请选择查询方式:\n";
            cin >> query_type;
            continue;
        }
        int start, end;
        cout << "----------------------------------------------------" << endl;
        cout << "(1)北京(2)西安(3)郑州(4)徐州(5)成都(6)广州(7)上海" << endl;
        cout << "----------------------------------------------------" << endl;
        cout << "请选择上面的城市序号:" << endl;
        cout << "起点城市:";
        cin >> start;
        cout << "终点城市:";
        cin >> end;
        if (start < 1 || start > vexsnumber || end < 1 || end > vexsnumber) {
            cout << "输入错误!!!" << endl;
            cout << endl;
            cout << "---------------------------" << endl;
            cout << "     请选择查询方式:\n";
            cin >> query_type;
            continue;
        }
        start--; // 转换为0-based索引
        end--;   // 转换为0-based索引
        switch (query_type) {
        case 1:
            cout << "--------------------------------------------------------------" << endl;
            cout << "最短距离为:" << endl;
            printPath(path_length, start, end);
            cout << "总距离为：" << dist_length[start][end] << " 公里" << endl;
            cout << "最短时间为:" << endl;
            printPath(path_time, start, end);
            cout << "总时间为：" << dist_time[start][end] << " 小时" << endl;
            cout << "最低费用为:" << endl;
            printPath(path_cost, start, end);
            cout << "总费用为：" << dist_cost[start][end] << " 元" << endl;
            cout << "最少中转次数查询:" << endl;
            BFS(APP, start, end);
            cout << "--------------------------------------------------------------" << endl;
            break;
        case 0:
            delete APP;
            return;
        }
        cout << endl;
        cout << "------------------------------" << endl;
        cout << "     请选择查询方式:\n";
        cin >> query_type;
    }
    delete APP;
}
int main() {
    menu(); // 菜单
    return 0;
}

参考结果:

-------------------------------------------------
        请选择查询方式:
        1. 输入起点与终点进行查询
        2. 清空查询记录
        0. 退出交通查询系统
-------------------------------------------------
---------------------------------------
     请输入起点与终点进行查询:
1
----------------------------------------------------
(1)北京(2)西安(3)郑州(4)徐州(5)成都(6)广州(7)上海
----------------------------------------------------
请选择上面的城市序号:
起点城市:1
终点城市:5
--------------------------------------------------------------
最短距离为:
北京 -> 郑州 -> 西安 -> 成都
总距离为：2018 公里
最短时间为:
北京 -> 郑州 -> 西安 -> 成都
总时间为：6.8 小时
最低费用为:
北京 -> 郑州 -> 西安 -> 成都
总费用为：633 元
最少中转次数查询:
从 北京 到 成都 的最少中转次数路径为：北京 -> 西安 -> 成都
总中转次数为：1 次
--------------------------------------------------------------

------------------------------
     请选择查询方式:
1
----------------------------------------------------
(1)北京(2)西安(3)郑州(4)徐州(5)成都(6)广州(7)上海
----------------------------------------------------
请选择上面的城市序号:
起点城市:4
终点城市:7
--------------------------------------------------------------
最短距离为:
徐州 -> 上海
总距离为：349 公里
最短时间为:
徐州 -> 上海
总时间为：1.2 小时
最低费用为:
徐州 -> 上海
总费用为：112 元
最少中转次数查询:
从 徐州 到 上海 的最少中转次数路径为：徐州 -> 上海
总中转次数为：0 次
--------------------------------------------------------------

------------------------------
     请选择查询方式:
1
----------------------------------------------------
(1)北京(2)西安(3)郑州(4)徐州(5)成都(6)广州(7)上海
----------------------------------------------------
请选择上面的城市序号:
起点城市:2
终点城市:4
--------------------------------------------------------------
最短距离为:
西安 -> 郑州 -> 徐州
总距离为：860 公里
最短时间为:
西安 -> 郑州 -> 徐州
总时间为：2.7 小时
最低费用为:
西安 -> 郑州 -> 徐州
总费用为：260 元
最少中转次数查询:
从 西安 到 徐州 的最少中转次数路径为：西安 -> 北京 -> 徐州
总中转次数为：1 次
--------------------------------------------------------------

------------------------------
     请选择查询方式:
0