求起始点1到N的最短路径.多组测试数据，对于每组数据 第一行是两个整数N， M。分别代表定点的数个和边的关系的个数。 从第二行至M+1行，每行三个整数，start, end, value。代表，节点start，节点end之间有一条长度为value的无向边。求1到N的最短路径。 (M, N, start, end, value < 100)对于每组测试数据，输出一个整数result，代表1至N的最短路径的value。c++实现

以下是使用 C++ 实现 Dijkstra 算法求解起点到终点的最短路径的代码：

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

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

int main() {
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) {
            break;
        }
        vector<vector<pair<int, int>>> graph(n);
        for (int i = 0; i < m; i++) {
            int start, end, value;
            cin >> start >> end >> value;
            graph[start-1].push_back(make_pair(end-1, value));
            graph[end-1].push_back(make_pair(start-1, value));
        }
        int result = dijkstra(graph, 0, n-1);
        cout << result << endl;
    }
    return 0;
}

时间复杂度为 O(mlogn)，其中 n 和 m 分别为顶点数和边数。