c++实现 7-2 单源最短路径 请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点，编号为0至n-1，以顶点0作为源点。 输入格式: 输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过1000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。 输出格式: 输出为一行整数，为按顶点编号顺序排列的源点0到各顶点的最短路径长度（不含源点到源点），每个整数后一个空格。如源点到某顶点无最短路径，则不输出该条路径长度。 输入样例: 4 4 0 1 1 0 3 1 1 3 1 2 0 1 输出样例: 1 1 代码长度

下面是使用Dijkstra算法求解单源最短路径的C++代码实现，时间复杂度为O(ElogV)：

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

using namespace std;

const int INF = INT_MAX;

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

    vector<vector<pair<int, int>>> graph(n);
    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
    }

    vector<int> dist(n, INF);
    dist[0] = 0;
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) {
            continue;
        }
        visited[u] = true;
        for (auto p : graph[u]) {
            int v = p.first;
            int w = p.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 1; i < n; i++) {
        if (dist[i] == INF) {
            cout << -1 << " ";
        } else {
            cout << dist[i] << " ";
        }
    }

    return 0;
}

其中，dist数组表示源点0到各个顶点的最短路径长度，visited数组表示该顶点是否已经被访问过。pq优先队列用于维护一个小根堆，每次取出堆顶的元素表示到某个顶点的最短路径已经确定。在更新每个顶点的最短路径时，如果发现新的路径比原来的路径更短，则更新dist数组并将该顶点加入小根堆中。