Dijkstra求单源最短路

这道题目采用邻接矩阵储存稠密图。

 
#include <iostream>
#include <queue>
#include <cstring>
 
using namespace std;
 
const int N = 1e05 + 10;
 
inline int read() {
	int res = 0, flag = 1;
	char c;
	c = getchar();
	while (!isdigit(c)) {
		if(c == '-') {
			flag = -1;
		} else flag = 1;
		c = getchar();
	}
	while (isdigit(c)) {
		res = (res << 1) + (res << 3) + (c ^ 48);
		c = getchar();
	}
 
	return res * flag;
}
 
const int M = 510;
int g[M][M];
int n, m;
int dist[M];
bool st[M];
 
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
	for (int i = 0; i < n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++) {
			if (!st[j] && (t == -1 || dist[j] < dist[t]))
				t = j;
		}
		st[t] = true;
		for (int j = 1; j <= n; ++j) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
	}
	if (dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];
}
 
int main() {
	memset(g, 0x3f, sizeof g);
	n = read();
	m = read();
	while (m --) {
		int a, b, c;
		a = read();
		b = read();
		c = read();
		g[a][b] = min(g[a][b], c);
	}
	cout << dijkstra();
 
	return 0;
 
}

g[M][M]存储邻接表。

dist[M]存储每一个点到原点的距离。dist[1] = 0；

st[M]表示这个点是否曾经被用作更新其他点过。

1:memset g和dist， 将两个点之间的距离和点到原点的距离设置为0x3f3f3f3f;

2:函数内部dijkstra() ： 首先要将dist[1]设置为零， 然后由于有n个点，我们需要更新n次， 所以写n个大循环

3:每次寻找之前没有用于更新过其他的点，并且距离原点最近的点的坐标t

4:用dist[t]去更新其他点的距离： dist[j] = min(dist[t] + g[t][j], dist[j]).      //这一步需要好好理解dist和g代表的含义

然后返回dist[n]， 如果dist[n] == 0x3f3f3f3f，也就是说没有被更新过，就说明没有到n点的最短路。