c++用临边多重表写一个迪杰斯特拉算法

以下是使用临边多重表实现的Dijkstra算法的C++代码：

#include <iostream>
#include <climits>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 100; // 最大顶点数

// 定义邻接表的边结构体
struct Edge {
    int to;    // 边的终点
    int w;     // 边的权重
    int next;  // 指向下一条边的指针
};

vector<Edge> edges(MAX * 2); // 边数组
int head[MAX];               // 邻接表的头指针数组
int num = 0;                 // 边的数量

// 添加一条边
void addEdge(int from, int to, int w) {
    edges[++num].to = to;
    edges[num].w = w;
    edges[num].next = head[from];
    head[from] = num;
}

// Dijkstra算法
void dijkstra(int s, int n) {
    int dist[MAX];          // 存储源点到各个顶点的最短距离
    bool vis[MAX] = {false}; // 标记顶点是否已被访问

    // 初始化dist数组和vis数组
    for (int i = 0; i <= n; i++) {
        dist[i] = INT_MAX;
    }
    dist[s] = 0;

    // 使用最小堆优化的Dijkstra算法
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) {
            continue;
        }
        vis[u] = true;
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].to;
            int w = edges[i].w;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    // 输出最短路径
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INT_MAX) {
            cout << "INF" << endl;
        } else {
            cout << dist[i] << endl;
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s; // n是顶点数，m是边数，s是源点编号
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w; // 输入边的起点，终点和权重
        addEdge(u, v, w);
        addEdge(v, u, w); // 无向图需要加上反向边
    }
    dijkstra(s, n);
    return 0;
}

其中，`addEdge()`函数用于添加一条边，`dijkstra()`函数用于实现Dijkstra算法，`main()`函数用于读入图的信息并调用`dijkstra()`函数求解最短路径。