用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 <cstring>
using namespace std;

const int INF = 0x3f3f3f3f; // 表示正无穷

struct Edge {
    int from, to, weight;
    Edge(int _from, int _to, int _weight) {
        from = _from;
        to = _to;
        weight = _weight;
    }
};

vector<Edge> edges; // 存储边的信息
int dist[1005]; // 存储每个点到源点的最短距离
int pre[1005]; // 存储每个点在最短路径上的前驱节点

bool BellmanFord(int n, int m, int src) {
    memset(dist, INF, sizeof(dist));
    memset(pre, -1, sizeof(pre));
    dist[src] = 0; // 源点距离为0

    // 进行n-1次松弛操作
    for (int i = 1; i < n; i++) {
        bool flag = false;
        for (int j = 0; j < m; j++) {
            int u = edges[j].from, v = edges[j].to, w = edges[j].weight;
            if (dist[u] != INF && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pre[v] = u;
                flag = true;
            }
        }
        if (!flag) return true; // 如果没有更新，则退出循环
    }

    // 进行第n次松弛操作
    for (int i = 0; i < m; i++) {
        int u = edges[i].from, v = edges[i].to, w = edges[i].weight;
        if (dist[u] != INF && dist[v] > dist[u] + w) {
            return false; // 存在负权回路
        }
    }
    return true;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        char u, v;
        int w;
        cin >> u >> v >> w;
        edges.push_back(Edge(u-'a', v-'a', w));
    }

    if (BellmanFord(n, m, 0)) { // 返回true表示不存在负权回路
        for (int i = 1; i < n; i++) {
            cout << dist[i] << ": " << (char)(0+'a');
            printPath(i);
            cout << endl;
        }
    } else {
        cout << "Negative-weight cycle found in the graph" << endl;
    }

    return 0;
}

需要注意的地方有：

1. 由于顶点是小写字母，因此需要将其转化为0-25的数字表示。
2. 在输出路径时，需要将数字转化为字母，输出时加上'a'即可。