最少点路径c++

输入

/*8
0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 0 0 0 0 1 1
0 1 0 0 0 1 0 0
0 1 0 0 0 1 0 0
0 0 0 1 1 0 0 0
0 0 1 0 0 0 0 1
0 0 1 0 0 0 1 0
4 7*/

输出

/*4-2-1-3-7*/

这个问题可以使用图中的最短路径算法来解决，比如Dijkstra算法或者Floyd算法。下面给出一个使用Dijkstra算法的示例代码来求解最短路径：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e9;  // 表示无穷大

void dijkstra(vector<vector<int>>& graph, int start, int end) {
    int n = graph.size();
    vector<int> dist(n, INF);  // 存储起点到每个村庄的最短距离
    vector<int> prev(n, -1);  // 存储最短路径上每个村庄的前一个村庄
    vector<bool> visited(n, false);  // 标记已经访问过的村庄

    dist[start] = 0;

    for (int i = 0; i < n; i++) {
        int u = -1;
        // 选择未访问过且距离最短的村庄作为当前村庄
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }

        if (u == -1) break;  // 所有村庄都已访问过

        visited[u] = true;

        // 更新与当前村庄相邻的村庄的最短距离
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] == 1 && dist[u] + 1 < dist[v]) {
                dist[v] = dist[u] + 1;
                prev[v] = u;
            }
        }
    }

    // 输出最短路径
    vector<int> path;
    int u = end;
    while (u != -1) {
        path.push_back(u + 1);
        u = prev[u];
    }
    reverse(path.begin(), path.end());

    for (int i = 0; i < path.size(); i++) {
        cout << path[i];
        if (i < path.size() - 1) {
            cout << "-";
        }
    }
}

int main() {
    int n;
    cin >> n;

    vector<vector<int>> graph(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }

    int s, t;
    cin >> s >> t;

    dijkstra(graph, s - 1, t - 1);

    return 0;
}

该代码使用了邻接矩阵来表示图，具体算法实现使用了Dijkstra算法。输入格式要与题目描述中给出的输入格式一致。

我的代码使用了Dijkstra算法来求解从起点s到终点t的最短路径。下面是每个函数的主要功能解释：

1. `dijkstra` 函数：该函数接受一个邻接矩阵表示的图 `graph`，起点 `start` 和终点 `end` 作为参数。它使用Dijkstra算法来计算从起点到终点的最短路径，并输出最短路径。

2. `dist`：该数组用于保存起点到每个村庄的最短距离。初始时，所有距离都设置为无穷大。

3. `prev`：该数组用于保存最短路径上每个村庄的前一个村庄。通过回溯这个数组，可以得到最短路径。

4. `visited`：该数组用于标记已经访问过的村庄。

算法的步骤如下：

- 首先，初始化距离数组 `dist`，起点到起点的距离为0，其他村庄的距离设置为无穷大。
- 然后，循环n次，每次选择一个未访问过且距离最短的村庄作为当前村庄，将其标记为已访问。
- 遍历与当前村庄相邻的村庄，如果该村庄未访问过且通过当前村庄可以找到更短的路径，则更新距离数组 `dist` 和前一个村庄数组 `prev`。
- 循环结束后，最短路径已经计算完成，通过回溯 `prev` 数组，可以得到从起点到终点的最短路径，并将其输出。

最后，通过 `main` 函数读取输入数据，构建邻接矩阵表示的图，并调用 `dijkstra` 函数求解最短路径。注意，输入的村庄编号是从1开始的，而在代码中使用的是从0开始的索引，所以在调用函数时需要将输入的s和t都减去1。

正好结果是4-2-1-3-7