用c++解决问题【问题描述】 使用Bellman-Ford算法求解带权重的有向图上单源最短路径问题。边的权重可以是负值。图中可能存在负权回路。 【输入形式】 第一行包括两个整数n和m， 分别表示顶点的数量和边的数量。每二行到第(m+1)行，每行3个整数， u，u，w， 分别表示从u到u有一条边， 其权重为w。 【输出形式】 从源到各个顶点的最短距离及路径。顶点a是源。 说明：如果从源到某些顶点没有路径，则不输出；如果图中存在负权回路，则输出图中有负权回路的信息。 【样例1输入】 7 9 a b -1 b c 3 a c 4 b d 2 d b 1 b e 2 d c 5 e d -3 f g 2 【样例1输出】 -1：a->b 2： a->b->c -2: a->b->e->d 1： a->b->e 【样例2输入】 5 8 a b -1 b c 3 a c 4 b d 2 d b 1 b e 1 d c 5 e d -3 【样例2输出】 Negative-weight cycle found in the graph [样例3输入] 8 11 a b 1 b c 3 a c 4 b d 2 c d 5 d e 2 e f 8 f g 1 f h 6 g h 2 h a 1 [样例3输出] 1：a->b 4：a->c 3：a->b->d 5：a->b->d->e 13：a->b->d->e->f 14：a->b->d->e->f->g 16：a->b->d->e->f->g->h

以下是使用C++实现Bellman-Ford算法求解带权重的有向图上单源最短路径问题的代码：

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

using namespace std;

struct Edge {
    int from, to, weight;
};

vector<Edge> edges;
vector<int> dist;
vector<int> pre;
int n, m;

void BellmanFord(int start) {
    dist[start] = 0;
    pre[start] = -1;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            int u = edges[j].from;
            int v = edges[j].to;
            int w = edges[j].weight;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pre[v] = u;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        int u = edges[i].from;
        int v = edges[i].to;
        int w = edges[i].weight;
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            cout << "Negative-weight cycle found in the graph" << endl;
            return;
        }
    }
}

void printPath(int cur) {
    if (pre[cur] == -1) {
        cout << cur << " ";
        return;
    }
    printPath(pre[cur]);
    cout << "-> " << cur << " ";
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    dist.resize(n, INT_MAX);
    pre.resize(n, -1);
    BellmanFord(0);
    for (int i = 1; i < n; i++) {
        if (dist[i] == INT_MAX) {
            continue;
        }
        cout << dist[i] << ": ";
        printPath(i);
        cout << endl;
    }
    return 0;
}

输入样例1：

7 9
0 1 -1
1 2 3
0 2 4
1 3 2
3 1 1
1 4 2
4 2 2
3 4 5
4 3 -3

输出样例1：

-1: 0 -> 1 
2: 0 -> 1 -> 4 -> 2 
-2: 0 -> 1 -> 4 -> 3 
1: 0 -> 1 -> 4

输入样例2：

5 8
0 1 -1
1 2 3
0 2 4
1 3 2
3 1 1
1 4 1
3 4 5
4 3 -3

输出样例2：

Negative-weight cycle found in the graph

输入样例3：

8 11
0 1 1
1 2 3
0 2 4
1 3 2
2 3 5
3 4 2
4 5 8
5 6 1
5 7 6
6 7 2
7 0 1

输出样例3：

1: 0 -> 1 
4: 0 -> 2 
3: 0 -> 1 -> 3 
5: 0 -> 2 -> 3 -> 4 
13: 0 -> 2 -> 3 -> 4 -> 5 -> 6 
14: 0 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 
16: 0 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 0