dijkstra算法c++代码

以下是Dijkstra算法C++代码的基本框架：

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

using namespace std;

const int MAXN = 10005;
const int INF = 0x3f3f3f3f;

int n, m, s;
int dis[MAXN];
bool vis[MAXN];
vector<pair<int, int> > G[MAXN];

void dijkstra(int s)
{
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[s] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;
    que.push(make_pair(0, s));

    while (!que.empty()) {
        int u = que.top().second;
        que.pop();

        if (vis[u]) continue;
        vis[u] = true;

        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].first;
            int w = G[u][i].second;

            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                que.push(make_pair(dis[v], v));
            }
        }
    }
}

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

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(make_pair(v, w));
    }

    dijkstra(s);

    for (int i = 1; i <= n; i++) {
        if (dis[i] == INF) {
            cout << "INF" << endl;
        } else {
            cout << dis[i] << endl;
        }
    }

    return 0;
}

在这个代码中，我们使用了一个vector数组来表示图，其中G[i]表示节点i的邻接表。我们还使用了一个pair<int, int>类型的vector来存储每个节点的邻居和对应的边权重。在dijkstra函数中，我们使用了一个优先队列来存储每个节点和对应的距离，其中距离小的节点优先级更高。在循环中，我们每次取出队列中距离最小的节点，并将其标记为已访问。然后，我们遍历该节点的所有邻居，并尝试通过该节点更新它们的距离。如果某个邻居的距离被更新，则将其加入优先队列以便后续处理。最后，我们输出每个节点到起点的最短距离。