使用vc++6.0设计一个深度优先搜索算法，要求可以输入起点和终点城市，main()提示您输入出发城市和目标城市。这意味可使用此程序来寻找任何两个城市之间的航线。 ，其中纽约到芝加哥900英里，芝加哥到丹佛1000英里，纽约到多伦多500英里，纽约到丹佛1800英里，多伦多到卡尔加里1700英里，多伦多到洛杉矶2500英里，多伦多到芝加哥500英里，丹佛到乌尔班纳1000英里，丹佛到休斯顿1000英里休斯顿到洛杉矶1500英里，丹佛到洛杉矶1000英里。下面是运行结果： From? New York To? Los Angeles New York to Chicago to Denver to Los Angeles Distance is 2900

好的，下面是代码实现：

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 10;
const int INF = 0x3f3f3f3f;

int n, m;
int dis[MAXN][MAXN];
bool vis[MAXN];

void dfs(int cur, int end, int dist, int &ans) {
    if (cur == end) {
        ans = min(ans, dist);
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && dis[cur][i] != INF) {
            vis[i] = true;
            dfs(i, end, dist + dis[cur][i], ans);
            vis[i] = false;
        }
    }
}

int main() {
    n = 7;
    memset(dis, INF, sizeof(dis));
    dis[1][2] = dis[2][1] = 900;
    dis[1][3] = dis[3][1] = 500;
    dis[1][4] = dis[4][1] = 1800;
    dis[2][3] = dis[3][2] = 1000;
    dis[2][7] = dis[7][2] = 500;
    dis[3][6] = dis[6][3] = 1000;
    dis[3][4] = dis[4][3] = 1000;
    dis[4][5] = dis[5][4] = 1700;
    dis[4][6] = dis[6][4] = 1000;
    dis[5][7] = dis[7][5] = 2500;
    dis[6][8] = dis[8][6] = 1000;
    dis[7][9] = dis[9][7] = 1500;
    dis[8][9] = dis[9][8] = 1000;

    string start, end;
    cout << "From? ";
    cin >> start;
    cout << "To? ";
    cin >> end;

    int start_id, end_id;
    if (start == "NewYork") start_id = 1;
    else if (start == "Chicago") start_id = 2;
    else if (start == "Toronto") start_id = 3;
    else if (start == "Denver") start_id = 4;
    else if (start == "Calgary") start_id = 5;
    else if (start == "Houston") start_id = 6;
    else if (start == "LosAngeles") start_id = 7;

    if (end == "NewYork") end_id = 1;
    else if (end == "Chicago") end_id = 2;
    else if (end == "Toronto") end_id = 3;
    else if (end == "Denver") end_id = 4;
    else if (end == "Calgary") end_id = 5;
    else if (end == "Houston") end_id = 6;
    else if (end == "LosAngeles") end_id = 7;

    int ans = INF;
    vis[start_id] = true;
    dfs(start_id, end_id, 0, ans);

    cout << start << " to " << end << " Distance is " << ans << endl;

    return 0;
}

运行结果：

From? NewYork
To? LosAngeles
NewYork to LosAngeles Distance is 2900