各种最短路模板

朴素版dijkstra模板

思路:稠密图用领接矩阵存图，初始化领接矩阵为Inf,输入边相关信息，然后调用dijkstra模板，初始化dis数组为inf，dis起点设置为0，然后for循环枚举n次，每次选出距离最小的点，标记为使用过，再用这个点去更新其他点的最短距离,时间复杂度O(n2)

代码

#include <bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;

const int N = 550;

int n, m, g[550][550], dis[N], vis[N];

void dijstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[1 = 0;
    for (int i = 0; i < n; ++i) {
        int t = -1;
        for (int j = 1; j <= n; ++j) 
            if (!vis[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
            vis[t] = true;
            for (int k = 1; k <= n; ++k)
                dis[k] = min(dis[k], dis[t] + g[t][k]);
    }
} 

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
    }
    dijstra();
    if (dis[n] == 0x3f3f3f3f)
        cout << -1;
    else
        cout << dis[n];
    return 0;
}

堆优化dijktra模板

思路:采用领接表存图，vector，每次取出dis数组最小点，即路径最小的点，用堆(优先队列）来维护即可，时间复杂度O(mlogn)

代码

#include <bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef pair<int, int> PII;
const int N = 1e6 + 10;

int n, m, dis[N], vis[N];
vector<pair<int, int> > G[N];

void dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (vis[ver]) continue;
        vis[ver] = true;
        for (int i = 0; i < G[ver].size(); i++) {
            int j = G[ver][i].first;
            int w = G[ver][i].second;
            if (dis[j] > distance + w) {
                dis[j] = distance + w;
                heap.push({dis[j], j});
            }
        } 
    }
}


int main() {
    cin >> n >> m;
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        G[x].push_back(make_pair(y, z));
    }
    dijkstra();
    if (dis[n] == 0x3f3f3f3f)
        cout << -1;
    else
        cout << dis[n];


    return 0;
}