Dijkstra1(朴素版)c++

朴素版适用于点个数的数量级较小的，因为要开二维数组。

介绍

• 朴素版适用于点个数的数量级较小的，因为要开二维数组。

流程

• 找最小距离的点的时候不能找之前已经找到过的点。而且更新t的条件中dist[t]>dist[j]容易写错了，如果找到一个比当前的t节点还要小的节点就更新。
• 用完了要将这个t点状态st[t]=true变为true。
• 要注意最后返回的时候，如果dist[n]==0x3f3f3f3f那么就返回-1，否则就直接返回dist[n]。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
	memset(dist, 0x3f, sizeof dist);

	dist[1] = 0;

	for (int i = 0; i < n - 1; i ++ )
	{
		int t = -1;
		for (int j = 1; j <= n; j ++ )
		{
			if (!st[j] and (t == -1 or dist[t] > dist[j]))
				t = j;
		}

		for (int j = 1; j <= n; j ++ )
		{
			dist[j] = min(dist[j], dist[t] + g[t][j]);
		}
		st[t] = true;
	}

	if (dist[n] == 0x3f3f3f3f) return -1;
	else return dist[n];
}


int main()
{
	memset(g, 0x3f, sizeof g);

	cin >> n >> m;

	while(m -- )
	{
		int a, b, c;
		cin >> a >> b >> c;

		g[a][b] = min(g[a][b], c);
	}

	cout << dijkstra() << '\n';

	return 0;
}