洛谷7915

#include <iostream>
#include <cstdio>
using namespace std;
const int N= 1e6 + 50;
int T, n, a[N];
int f[N], d[N];
bool vis[N];
string ans;
void init() {
	scanf("%d", &n);
	for (int i = 1; i <= (n << 1); i++) scanf("%d", a + i);
	for (int i = 1; i <= (n << 1); i++) {
		//记录相同数字互相的位置 
		if (!vis[a[i]]) {
			vis[a[i]] = true;
			d[a[i]] = i;
		} else {
			f[d[a[i]]] = i;
			f[i] = d[a[i]];
		}
	}
}
void solve() {
	if (a[1] <= a[n << 1]) {
		ans = "L";
		int i = 2, j = (n << 1);
		int l = f[a[i]] - 1, r = f[a[i]] + 1;
		while (true) {
			if (l < i) m = 0;
			if (r > j) r = 0;
		}
	} else {
		ans = "R";
	}
}
int main() {
	scanf("%d", &T);
	while (T--) {
		init();
		solve();
	}
	return 0;
}

Kruskal:

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 5e5 + 50, F = 2e5 + 50;
int n, m, f[F];
struct Node{
	int u, v, w;
	bool operator<(const Node &P)const{
		return w < P.w;
	}
}a[N];
int Find(int x) {
	while (x != f[x]) x = f[x] = f[f[x]];
	return x;
}
ll ans = 0;
void Kruskal() {
	for (int i = 1; i <= n; i++) f[i] = i;
	sort(a + 1, a + m + 1);
	for (int i = 1; i <= m; i++) {
		int fx = Find(a[i].u), fy = Find(a[i].v);
		if (fx != fy) {
			ans += a[i].w;
			f[fx] = fy;
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &a[i].u, &a[i].v, &a[i].w);
	}
	
	Kruskal();
	
	printf("%lld", ans);
	return 0;
}

Prim:

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
#define ll long long
#define PII pair<int, int>
const int N = 2e5 + 50, M = 5e5 + 50;
int n, m, u, v, w;
ll ans = 0;
struct Node {
	int v, nxt, w;
} e[M << 1];
int head[M << 1], cnt = 0, num = 0;
bool vis[N];
void add(int u, int v, int w) {
	cnt++;
	e[cnt].w = w;
	e[cnt].v = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
	return ;
}
priority_queue<PII, vector<PII>, greater<PII> > Q;

void Prim() {
	//   长度  点位
	Q.push({0, 1});
	while (!Q.empty() && num < n) {
		PII tmp = Q.top();
		Q.pop();
		// 判断是否加入最小生成树, 如果加入，换下一个点
		while (vis[tmp.second] && !Q.empty()) {
			tmp = Q.top();
			Q.pop();
		}
		ans += (ll)tmp.first;
		num++;  //计数
		vis[tmp.second] = true; // 标记
		for (int i = head[tmp.second]; i; i = e[i].nxt) {
			if (!vis[e[i].v]) { // 如果还没加入最小生成树，则加入
				Q.push({e[i].w, e[i].v});
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &u, &v, &w);
		add(u, v, w);
		add(v, u, w);//无向图
	}
	Prim();
	cout << ans;
	return 0;
}

Dijsktra:

#include <iostream>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
#define ll long long
#define PII pair<int, int>
const int N = 2e4;
int n, m, S, T;
ll s, t, w;
struct Node{
	int v, w;
	int nxt;
}e[N];
int head[N], cnt, vis[N];
ll dis[N];
priority_queue<PII, vector<PII>, greater<PII> > Q;
void add(ll u, ll v, ll w) {
	// 建立联系 
	cnt++;
	e[cnt].w = w;
	e[cnt].v = v;
	e[cnt].nxt = head[u];
	head[u]  = cnt;
	return ;
}
void Dijsktra() {
	memset(dis, 0x3f3f3f, sizeof(dis)); // 初始化 最大值 
	Q.push({0, S}); // 从 S 开始找路，并且第一个数字表示当前点到 S 的距离 
	
	while (!Q.empty()) {
		PII tmp = Q.top(); // 取出 
		Q.pop(); // 删除 
		int now = tmp.second;
		int d = tmp.first;
		if (vis[now]) continue;
		/*
		Dijsktra 算法是对 边 进行优化，实质是贪心
		所以，如果这个点我来过，我就不在再对这个点进行遍历 
		*/ 
		vis[now] = true; // 标记，来过
		for (int i = head[now]; i; i = e[i].nxt) {
			int v = e[i].v, w = e[i].w; // 取出 
			
			if (dis[v] > d + w) { // 判断条件，结合图形理解 
				dis[v] = d + w;   // 更新最短路 
				Q.push({dis[v], v}); // 存入这个当前最短路径以及这个点 
			}
		}
	}
}

int main() {
	scanf("%d %d %d %d", &n, &m, &S, &T);
	for (int i = 1; i <= m; i++) {
		scanf("%lld %lld %lld", &s, &t, &w);
		// 建立联系 
		add(s, t, w);
		add(t, s, w);
	}
	Dijsktra();
	cout << dis[T];
	return 0;
}

Spfa:

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define ll long long
const int N = 2e4;
int n, m, S, T;
ll s, t, w;
struct Node{
	int v, w;
	int nxt;
}e[N];
int head[N], cnt, vis[N];
ll dis[N];
queue<int> Q;
void add(ll u, ll v, ll w) {
	cnt++;
	e[cnt].w = w;
	e[cnt].v = v;
	e[cnt].nxt = head[u];
	head[u]  = cnt;
	return ;
}
void spfa() {
	memset(dis, 0x3f3f3f, sizeof(dis));
	dis[S] = 0;
	Q.push(S);
	vis[S] = true;
	
	while (!Q.empty()) {
		int now = Q.front();
		Q.pop();
		
		vis[now] = false;
		/*
		spfa实际上是存的点，这样就和Dijsktra有所不同
		判断条件变为 这个点 i 如果在 容器 Q 中，vis[i] = true
		取出后或者不在容器里了，vis[i] = false 
		*/
		for (int i = head[now]; i; i = e[i].nxt) {
			int v = e[i].v, w = e[i].w;
			
			if (dis[v] > dis[now] + w) { // 同理，判断条件，理解不了就结合图形 
				dis[v] = dis[now] + w;
				if (!vis[v]) { // 如果这个点不在我的容器 Q 里面，就标记 并且 存入 
					vis[v] = true;
					Q.push(v);
				}
			}
		}
	}
}

int main() {
	scanf("%d %d %d %d", &n, &m, &S, &T);
	for (int i = 1; i <= m; i++) {
		scanf("%lld %lld %lld", &s, &t, &w);
		// 建立联系 
		add(s, t, w);
		add(t, s, w);
	}
	spfa();
	cout << dis[T];
	return 0;
}

Floyd:

#include <iostream>
#include <cstring>
using namespace std;
const int N = 3000;
int n, m, S, T;
int s, t, w;
int dp[N][N];
void Floyd() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}
int main() {
	scanf("%d %d %d %d", &n, &m, &S, &T);
	memset(dp, 0x3f3f3f, sizeof(dp));
	//初始化 
//	for (int i = 0; i < N; i++) 
//		for (int j = 0; j < N; j++) dp[i][j] = 1000000;
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &s, &t, &w);
		dp[s][t] = dp[t][s] = w;
		// 从 s -> t 的边权为 w，从 t -> s 的边权为 w 
	}

	Floyd();
	
	cout << dp[S][T]; // 输出从 S -> T 的单源最短路径 
	return 0;
}