代碼

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int vertex, weight;
};

class Graph {
private:
    int n;
    vector<Edge> * edges;
    bool * visited;
public:
    int * dist;
    Graph (int input_n) {
        n = input_n;
        edges = new vector<Edge>[n];
        dist = new int[n];
        visited = new bool[n];
        memset(visited, 0, n);
        memset(dist, 0x3f, n * sizeof(int));
    }
    ~Graph() {
        delete[] dist;
        delete[] edges;
        delete[] visited;
    }
    void insert(int x, int y, int weight) {
        edges[x].push_back(Edge{y, weight});
        edges[y].push_back(Edge{x, weight});
    }
    void dijkstra(int v) {
        dist[v]=0; //從v出發(fā)，首先將v的距離設(shè)置為0（自己到自己）
        for(int i=0;i<n;i++){ //遍歷所有其他結(jié)點
            int min_dist=INF,min_vertex;  //初始化一個最短距離和當(dāng)前距離最短的節(jié)點
            for(int j=0;j<n;j++){
                if(!visited[j]&&dist[j]<min_dist){ 如果當(dāng)前結(jié)點的距離比min_dist小則更新之
                    min_dist=dist[j];
                    min_vertex=j;
                }  
            }
            visited[min_vertex]=1;//標(biāo)記已訪問
            for (Edge& j:edges[min_vertex]){//遍歷min_vertex的每一條邊
                if(min_dist+j.weight<dist[j.vertex]){//如果當(dāng)前的最小距離，加上邊的距離小于j.vertex的距離的話就更新j.vertex的距離——這意味著j.vertex的距離沒那么大
                    dist[j.vertex]=min_dist+j.weight;
                }
            }
        }
        
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    Graph g(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g.insert(a, b, c);
    }
    g.dijkstra(0);
    for (int i = 0; i < n; i++) {
        cout << i << ": " << g.dist[i] << endl;
    }
    return 0;
}

Dijkstra算法的思路：
參見代碼注釋