Dijkstra based on priority queue

又来跑图了！

链式前向星

~(-1) = 0

#include <bits/stdc++.h>
#define N 100007
#define M 10000007
using namespace std;

struct node{
	int v, w, nxt;
}e[M];

int tot, hd[N];

inline void add(int u, int v, int w) {
	++tot;
	e[tot].v = v; e[tot].w = w;
	e[tot].nxt = hd[u];
	hd[u] = tot;
}

int main(){
	int m, n;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
	}
	return 0;
}

最短路径问题

Dijkstra

按最短路径的长度递增的次序，依次求得源点到其余各点的最短路径。

int tot, hd[N];

struct node {
    int v, w, nxt;
}e[M];

void add(int u, int v, int w) {
	++tot;
    e[tot].v = v; e[tot].w = w;
    e[tot].nxt = hd[u];
    hd[u] = tot;
}

int main(){
    int n = rd(), m = rd();
    for (int i = 1; i <= m; ++i) {
    	int u = rd(), v = rd(), w= rd();
        add(u, v, w); add(v, u, w);
    }
    
    return 0;
}

邻接矩阵实现

int a[N][N], dis[N], vis[N];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= m; ++i) {
    	int u = rd(), v = rd(), w= rd();
        a[u][v] = min(a[u][v], w);
        a[v][u] = min(a[v][u], w);
    }
    for (int i = 1; i <= n; ++i) {
        dis[i] = 100000;
    }
    dis[1] = 0;
    int pos= 1;
    for (int i = 1; i <= n; ++i) {
        int mn = 100000; vis[pos] = 1;
        for (int j = 1; j <= n; ++j) {
            if (a[pos][j] != 100000) dis[j] = min(dis[j], a[pos][j] + dis[pos]);
            if (!vis[j] && dis[j] < mn){
                mn = dis[j]; pos = j;
            }
        }
        if (mn == 100000) break;
    }
    cout << dis[n];
    return 0;
}

优先队列维护dis（堆优化

洛谷

struct edge{
	int v, w, nxt;
}e[M];

int tot, hd[N];

inline void add(int u, int v, int w) {
	++tot;
	e[tot].v = v; e[tot].w = w;
	e[tot].nxt = hd[u];
	hd[u] = tot;
}

struct node{
    int id, dis;
    bool operator < (const node &a) const {return a.dis < dis;}
};

int a[N][N], dis[N], vis[N];

void dij() {
    priority_queue<node> q;
    q.push(node{start, 0});
    for (int i = 1;i <= n; ++i) dis[i] = INF;
    dis[start] = 0;
	while (!q.empty()) {
        node a = q.top(); q.pop();
        int nw = a.id;
        if (vis[nw]) continue;
        vis[nw] = 1;
        for (int i = hd[nw]; i; i = e[i].nxt) {
            int j = e[i].v;
            if (dis[nw] + e[i].w < dis[j]) {
                dis[j] = dis[nw] + e[i].w;
                q.push(node{j, dis[j]});
            }
        }
    }
}