图论模板

一、Dijkstra 无负权图 O(mlogm)

#include <cstdio>
#include <cstring>
#include <queue>
#define max(a, b) (a > b ? a : b)
using namespace std;
const int N = 1e5 + 5, M = 1e5 + 5, INF = 0x3f3f3f3f;
struct E {
	int v, w, next;
}e[M];
struct Node {
	int v, d;
	Node(int v, int d):v(v), d(d){}
	bool operator < (const Node &w)const {
		return d > w.d;
	}
};
int n, m, len = 1, head[N], d[N];
bool vis[N];
void add(int u, int v, int w) {
	e[len].v = v;
	e[len].next = head[u];
	e[len].w = w;
	head[u] = len++;
}
void dijkstra(int u) {
	memset(d, 0x3f, sizeof(d));
	d[u] = 0;
	priority_queue<Node> q; 
	q.push(Node(u, 0));
	while (!q.empty()) {
		u = q.top().v;
		q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int j = head[u]; j; j = e[j].next) {
			int v = e[j].v;
			int w = e[j].w;
			if (!vis[v] && d[v] > d[u] + w) {
				d[v] = d[u] +w;
				q.push(Node(v, d[v]));
			}
		}
	}
}
int main() {
	scanf("%d%d", &n, &m);
	int u, v, w;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
	}
	dijkstra(1);
	printf("%d\n", d[n] == INF ? -1 : d[n]);
	return 0;
} 

二、Bellma_Ford 经过k条边的最短路 O(nm)

#include <cstdio>
#include <cstring>
#define min(a, b) (a > b ? b : a)
using namespace std;
const int N = 505, M = 1e4 + 5, INF = 0x3f3f3f3f;
struct E {
	int u, v, w;
}e[M];
int n, m, k, len, d[N], last[N]; //last防止发生串联 
void add(int u, int v, int w) {
	e[++len].u = u;
	e[len].v = v;
	e[len].w = w;
}
void Bellman_Ford(int u) {
	memset(d, 0x3f, sizeof(d));
	d[u] = 0;
	for (int i = 1; i <= k; i++) {
		memcpy(last, d, sizeof(d)); //拷贝上一次的结果 
		for (int i = 1; i <= m; i++) {
			int u = e[i].u;
			int v = e[i].v;
			int w = e[i].w;			
			d[v] = min(d[v], last[u] + w);
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	int u, v, w;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
	}
	Bellman_Ford(1);
	if (d[n] > INF / 2) printf("impossible");
	else printf("%d", d[n]);
	return 0;
} 

三、SPFA O(km) ~ O(nm)

#include <cstdio>
#include <cstring>
#include <queue>
#define max(a, b) (a > b ? a : b)
using namespace std;
const int N = 1e5 + 5, M = 1e5 + 5, INF = 0x3f3f3f3f;
struct E {
	int v, w, next;
}e[M];
struct Node {
	int v, d;
	Node(int v, int d):v(v), d(d){}
	bool operator < (const Node &w)const {
		return d > w.d;
	}
};
int n, m, len = 1, head[N], d[N];
bool vis[N];
void add(int u, int v, int w) {
	e[len].v = v;
	e[len].next = head[u];
	e[len].w = w;
	head[u] = len++;
}
void spfa(int u) {
	memset(d, 0x3f, sizeof(d));
	d[u] = 0;
 	queue<int> q;
 	q.push(u);
 	while (!q.empty()) {
 		u = q.front();
		q.pop();
		vis[u] = false;
		for (int j = head[u]; j; j = e[j].next) {
			int v = e[j].v;
			int w = e[j].w;
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
				if (!vis[v]) q.push(v), vis[v] = true;
			}
		}	
	}
}
int main() {
	scanf("%d%d", &n, &m);
	int u, v, w;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
	}
	spfa(1);
	if (d[n] == INF) printf("impossible");
	else printf("%d", d[n]);
	return 0;
} 

• 判断负环

#include <cstdio>
#include <cstring>
#include <queue>
#define max(a, b) (a > b ? a : b)
using namespace std;
const int N = 1e5 + 5, M = 1e5 + 5, INF = 0x3f3f3f3f;
struct E {
	int v, w, next;
}e[M];
struct Node {
	int v, d;
	Node(int v, int d):v(v), d(d){}
	bool operator < (const Node &w)const {
		return d > w.d;
	}
};
int n, m, len = 1, head[N], d[N], cnt[N]; // cnt判断入队次数 
bool vis[N];
void add(int u, int v, int w) {
	e[len].v = v;
	e[len].next = head[u];
	e[len].w = w;
	head[u] = len++;
}
bool spfa() {
 	queue<int> q;
 	for (int i = 1; i <= n; i++) q.push(i), vis[i] = true; //把所有点加进去
 	while (!q.empty()) {
 		int u = q.front();
		q.pop();
		vis[u] = false;
		for (int j = head[u]; j; j = e[j].next) {
			int v = e[j].v;
			int w = e[j].w;
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
				if (!vis[v]) {
					q.push(v);
					vis[v] = true;
					cnt[v]++; 
					if (cnt[v] > n) return true;
				}
			}
		}	
	}
	return false;
}
int main() {
	scanf("%d%d", &n, &m);
	int u, v, w;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
	}
	if (spfa()) printf("Yes");
	else printf("No"); 
	return 0;
} 

四、Floyd O(n^3)

#include <cstdio>
#include <cstring>
#define min(a, b) (a > b ? b : a)
using namespace std;
const int N = 205, INF = 0x3f3f3f3f;
int g[N][N], n, m , k, u, v, w;
void floyd() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
      			g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}	
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
	    for (int j = 1; j <= n; j++) {
	        if (i == j) g[i][j] = 0; //自环 直接删去 因为自环肯定是正边 
	        else g[i][j] = INF;
	    }
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		g[u][v] = min(g[u][v], w);
	}
	floyd();
	while (k--) {
		scanf("%d%d", &u, &v);
		if (g[u][v] > INF / 2) { //因为负权边的原因 
			printf("impossible\n");
		} else {
			printf("%d\n", g[u][v]);
		}
	}
	return 0;
}