c++ 图求源点到图中每个点的最短路径 然后输出

可以使用 Dijkstra 算法来求解源点到图中每个点的最短路径，具体步骤如下：

1. 初始化距离数组 dist，将源点到每个点的距离初始化为一个较大的值。
2. 将源点加入到最短路径集合 S 中，更新源点到相邻节点的距离。
3. 选择距离最小的节点 u，加入到最短路径集合 S 中，并更新 u 的相邻节点的距离。
4. 重复步骤 3 直到所有节点都加入到最短路径集合 S 中，或者源点无法到达某些节点。

下面是使用 C++ 实现 Dijkstra 算法的代码：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INF);
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push(make_pair(0, start));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push(make_pair(dist[v], v));
            }
        }
    }
    return dist;
}

int main() {
    int n, m, start;
    cin >> n >> m >> start;
    vector<vector<pair<int, int>>> graph(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back(make_pair(v, w));
    }
    vector<int> dist = dijkstra(graph, start);
    for (int i = 0; i < n; ++i) {
        if (dist[i] == INF) {
            cout << "INF" << endl;
        } else {
            cout << dist[i] << endl;
        }
    }
    return 0;
}

其中，输入的第一行包含三个整数 n、m、start，分别表示节点数、边数和源点的编号。接下来 m 行输入每条边的起点、终点和权值。输出源点到每个点的最短距离，如果无法到达某个点，则输出 INF。