问题描述

稠密图使用朴素版Dijkstra算法

• 使用邻接矩阵存储图
• 定义dist[]数组用来表示图中所有点到1号点的距离，初始化所有点到1号点的距离为0x3f3f3f3f，dist[1] = 0
• 循环n次

1. 在图中找出距离1号点最小的点，并且当前点没有被确定过，另存为t
2. 将当前点进行标记，被确定了
3. 遍历t点指向的其他点j，如果dist[j] > dist[t] + 边权，更新dist[j]为dist[t] + 边权

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];		// 邻接矩阵存储稠密图
int dist[N];		// 图中点到1号点的距离
bool st[N];			// 将已经判断的点进行标记

int dijkstra()
{
	memset(dist, 0x3f, sizeof dist);	// 初始化0x3f3f3f3f
	dist[1] = 0;	// 1号点到1号点的距离为0
	for(int i = 0; i < n; i++)	// n次循环
	{
		int t = -1;		// 找到图中未判断的点到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++)		// 更新t号点指向的点到1号点的距离
		{
			dist[j] = min(dist[j], dist[t] + g[t][j]);
		}
	}
	if(dist[n] == 0x3f3f3f3f) return -1;
	else return dist[n];
}

int main()
{
	scanf("%d%d", &n, &m);
	memset(g, 0x3f, sizeof g);
	for(int i = 0;i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		g[a][b] = min(g[a][b], c);	// 处理重边
	}
	int res = dijkstra();
	
	printf("%d\n", res);
	
	return 0;
}