用c++代码求出有n(1<=n<=600)个结点有向图中，结点1到结点n的最短路径,输入格式:第一行有 2 个整数n,m,接下来m行每行有三个整数u,v,w,结点u到v有一条权为w的边(w<10^6)。 输出格式:输出结点1到结点n之间的最短路径，如果1到n之间不存在路径，输出-1。

以下是使用 Dijkstra 算法求解该问题的 C++ 代码：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

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

    // 初始化邻接表
    vector<pair<int, int>> graph[n];
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u-1].push_back({v-1, w});
    }

    // Dijkstra 算法
    int dist[n];
    memset(dist, INF, sizeof(dist));
    dist[0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    heap.push({0, 0});
    while (!heap.empty()) {
        int d = heap.top().first;
        int u = heap.top().second;
        heap.pop();
        if (d > dist[u]) {
            continue;
        }
        for (auto p : graph[u]) {
            int v = p.first;
            int w = p.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                heap.push({dist[v], v});
            }
        }
    }

    // 输出结果
    if (dist[n-1] == INF) {
        cout << -1 << endl;
    } else {
        cout << dist[n-1] << endl;
    }

    return 0;
}

代码解释：

- 首先读入输入的 n 和 m，表示图中有 n 个结点和 m 条边。
- 然后用邻接表存储图的信息。
- 初始化距离数组 dist，其中 dist[i] 表示结点 1 到结点 i+1 的最短路径长度，初始值为 INF。
- 将结点 1 加入堆中（堆中元素为 (dist[u], u)），表示结点 1 到结点 1 的距离为 0。
- 每次从堆中取出距离最短的结点 u，遍历其所有邻居结点 v，如果从结点 1 到结点 v 的距离可以通过从结点 1 到结点 u 的距离加上 u 到 v 的距离来更新，则更新 dist[v] 的值，并将 (dist[v], v) 加入堆中。
- 最后输出 dist[n-1] 的值，即为结点 1 到结点 n 的最短路径长度。

如果图中存在负权边，可以使用 Bellman-Ford 算法来解决，以下是使用 Bellman-Ford 算法解决该问题的代码：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

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

    // 初始化邻接表
    vector<pair<int, int>> graph[n];
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u-1].push_back({v-1, w});
    }

    // Bellman-Ford 算法
    int dist[n];
    memset(dist, INF, sizeof(dist));
    dist[0] = 0;
    for (int i = 0; i < n-1; i++) {
        for (int u = 0; u < n; u++) {
            for (auto p : graph[u]) {
                int v = p.first;
                int w = p.second;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }

    // 判断是否存在负环
    bool has_negative_cycle = false;
    for (int u = 0; u < n; u++) {
        for (auto p : graph[u]) {
            int v = p.first;
            int w = p.second;
            if (dist[u] + w < dist[v]) {
                has_negative_cycle = true;
                break;
            }
        }
        if (has_negative_cycle) {
            break;
        }
    }

    // 输出结果
    if (has_negative_cycle) {
        cout << -1 << endl;
    } else {
        cout << (dist[n-1] == INF ? -1 : dist[n-1]) << endl;
    }

    return 0;
}

代码解释：

- 首先读入输入的 n 和 m，表示图中有 n 个结点和 m 条边。
- 然后用邻接表存储图的信息。
- 初始化距离数组 dist，其中 dist[i] 表示结点 1 到结点 i+1 的最短路径长度，初始值为 INF。
- 进行 n-1 轮松弛操作，每轮遍历所有边，如果从结点 1 到结点 v 的距离可以通过从结点 1 到结点 u 的距离加上 u 到 v 的距离来更新，则更新 dist[v] 的值。
- 最后判断是否存在负环，如果存在，则说明无法求出最短路径；否则输出 dist[n-1] 的值，即为结点 1 到结点 n 的最短路径长度。如果 dist[n-1] 的值为 INF，则说明结点 1 无法到达结点 n，输出 -1。