最短路径Dijkstra模板

最短路径Dijkstra模板

2019年11月5日 0 作者 lnkkerst


SPFA已死

就这样(不给博主面子),提供链式前向星写法和邻接表写法。

链式前向星+priority_queue

<pre class="wp-block-syntaxhighlighter-code">#include <cstdio>
#include <cctype>
#include <queue> //头文件要恰着用
using namespace std;

struct Edge {
	int v, w, nex;
} edges[4000010];
//储存边的信息

struct Node {
	int h, dis; 
	bool vis;
} nodes[1000010];
//储存点的信息

int n, m, s, cnt; //依次为点的个数,边的个数,起点编号,加边时用的统计变量

int read() {
	int ret, f = 1;
	char ch;
	while(!isdigit(ch = getchar())) (ch == '-') && (f = -1);
	for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');
	return ret * f;
}
//快读板子

void print(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
//快输板子

void addedge(int u, int v, int w) {
	edges[++cnt] = (struct Edge){v, w, nodes[u].h};
	nodes[u].h = cnt;
}
//加边

void dij(int s) {
	for(int i = 1; i <= n; ++i) nodes[i].dis = (int)1e9;
	nodes[s].dis = 0;
	priority_queue<pair<int, int >, vector<pair<int, int > >, greater<pair<int, int > > > heap;
	heap.push(make_pair(nodes[s].dis, s));
	while(!heap.empty()) {
		int u = heap.top().second;
		heap.pop();
		if(nodes[u].vis) continue;
		nodes[u].vis = 1;
		for(int i = nodes[u].h; i; i = edges[i].nex) 
			if(nodes[u].dis + edges[i].w < nodes[edges[i].v].dis) {
				nodes[edges[i].v].dis = nodes[u].dis + edges[i].w;
				if(!nodes[edges[i].v].vis)
                    heap.push(make_pair(nodes[edges[i].v].dis, edges[i].v));
			}
	} 
}
//Dijkstra板子

int main() {
	n = read(), m = read(), s = read();
	for(int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        addedge(u, v, w);
    } dij(s);
	for(int i = 1; i <= n; ++i) print(nodes[i].dis), putchar(' ');
	return 0;
}</pre>

链式前向星+set 实测还是priority_queue更快

<pre class="wp-block-syntaxhighlighter-code">#include <cstdio>
#include <cctype>
#include <set> //头文件要恰着用
using namespace std;

struct Edge {
	int v, w, nex;
} edges[4000010];
//储存边的信息

struct Node {
	int h, dis; 
	bool vis;
} nodes[1000010];
//储存点的信息

int n, m, s, cnt; //依次为点的个数,边的个数,起点编号,加边时用的统计变量

int read() {
	int ret, f = 1;
	char ch;
	while(!isdigit(ch = getchar())) (ch == '-') && (f = -1);
	for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');
	return ret * f;
}
//快读板子

void print(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
//快输板子

void addedge(int u, int v, int w) {
	edges[++cnt] = (struct Edge){v, w, nodes[u].h};
	nodes[u].h = cnt;
}
//加边

void dij(int s) {
	for(int i = 1; i <= n; ++i) nodes[i].dis = (int)1e9;
	nodes[s].dis = 0;
	set<pair<int, int > > heap;
	for(int i = 1; i <= n; ++i) heap.insert(make_pair(nodes[i].dis, i));
	while(!heap.empty()) {
		int d = heap.begin()->first;
		int u = heap.begin()->second;
		heap.erase(heap.begin());
		if(d > nodes[u].dis) continue;
		for(int i = nodes[u].h; i; i = edges[i].nex) 
			if(nodes[u].dis + edges[i].w < nodes[edges[i].v].dis) {
				nodes[edges[i].v].dis = nodes[u].dis + edges[i].w;
				heap.insert(make_pair(nodes[edges[i].v].dis, edges[i].v));
			}
	} 
}
//Dijkstra板子

int main() {
	n = read(), m = read(), s = read();
	for(int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        addedge(u, v, w);
    } dij(s);
	for(int i = 1; i <= n; ++i) print(nodes[i].dis), putchar(' ');
	return 0;
}</pre>

邻接表+priority_queue

<pre class="wp-block-syntaxhighlighter-code">#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAXN 100010
#define MAXM 200010

int n, m, s;

struct Node {
    std::vector<struct Edge> edges;
    int dist;
} nodes[MAXN + 1];

struct Edge {
    Node *from, *to;
    int w;
};

void add(int u, int v, int w) {
    Edge e;
    e.from = &nodes[u];
    e.to = &nodes[v];
    e.w = w;
    nodes[u].edges.push_back(e);
}

void dijkstra(int start) {
    for(int i = 1; i <= n; i++)
        nodes[i].dist = __INT_MAX__;
    std::priority_queue<std::pair<int, Node*> > q;
    q.push(std::make_pair(0, &nodes[start]));
    nodes[start].dist = 0;
    while(!q.empty()) {
        std::pair<int, Node *> p = q.top();
        q.pop();
        if(-p.first != p.second->dist)
            continue;
        Node *v = p.second;
        for(int i = 0; i < (int)v->edges.size(); i++) {
            Edge *e = &v->edges[i];
            if(e->to->dist > v->dist + e->w) {
                e->to->dist = v->dist + e->w;
                q.push(std::make_pair(-e->to->dist, e->to));
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1; i <= m; i++) {
        int t1, t2, t3;
        scanf("%d%d%d", &t1, &t2, &t3);
        add(t1, t2, t3);
    }
    dijkstra(s);
    for(int i = 1; i <= n; i++)
        printf("%d ", nodes[i].dist);
    return 0;
	}</pre>

(其实我分不清啥是链式前向星啥是邻接表)