最短路径（dijistra和floyd算法）

以2021年合肥学院校赛E题为例

题目描述
zs王国中有n个城镇，在这些城镇之间有m条路，bs需要从1号城镇出发去n号城镇完成他的使命，现在请你规划一条路径，使bs走的路径最短，输出最短路径长度，若不能达到n号城镇输出“-1”。
输入描述:
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出描述:
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1

样例输入

3 3
1 2 2
2 3 1
1 3 4

样例输出

3

备注:
1≤n≤500,
1≤m≤100000,
图中涉及边长均不超过10000。

这道题就是一道最短路径板子题
dijistra算法

#include
using namespace std;
const int INF = INT_MAX;
const int maxn = 1e3;
int G[maxn][maxn];
int d[maxn],n,m;
bool visited[maxn] = {false};
void dijistra() {
	fill(d, d + maxn, INF);
	d[1] = 0;//起点到起点的距离为1 
	for(int i = 1; i <= n; i++) {
		int u = -1, MIN = INF;
		for(int j = 1; j <= n; j++) {
			if(visited[j] == false && d[j] < MIN) {
				u = j;
				MIN = d[j];
			}
		}
		if(u == -1) return;//找不到u，则起点到达不了剩下的点 
		visited[u] = true;
		for(int v = 1; v <= n; v++) {
			if(visited[v] == false && G[u][v] != INF && d[u] + G[u][v] < INF) 
				d[v] = d[u] + G[u][v];
		}
	}
} 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	fill(G[0], G[0] + maxn * maxn, INF);
	cin >> n >> m;
	while(m--) {
		int u,v,w;
		cin >> u >> v >> w;
		G[u][v] = min(G[u][v], w);//这里要这样写，直接写G[u][v]=w会WA，可能后台数据出现了重复的u v
	}
	dijistra();
	if(d[n] == INF) cout << -1;
	else cout << d[n];
	
	return 0;
}

floyd算法

#include
using namespace std;
const int INF = INT_MAX;
const int maxn = 1000;
int G[maxn][maxn];
int d[maxn],n,m;
bool visited[maxn] = {false};
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	fill(G[0], G[0] + maxn * maxn, INF);
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u,v,w;
		cin >> u >> v >> w;
		G[u][v] = min(G[u][v], w);
	}
	for(int i = 1; i <= n; i++) G[i][i] = 0;
	for(int k=1;k<=n;k++) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				if(G[i][k] != INF && G[k][j] != INF && G[i][k] + G[k][j] < G[i][j]) 
					G[i][j] = G[i][k] + G[k][j];
			}
		}
	}
	if(G[1][n] == INF)cout << -1;
	else cout << G[1][n];
	return 0;
}