dijkstra算法是解决单源最短路问题的重要算法
其主要思想如下:
- 维护一个集合s,其元素是已经确定最短路距离的点
- 维护一个数组d[i],代表起点到i的最短距离,初始化全部为无穷大,起点的d为0
- 每次选择一个不在集合s中,离起点最近的点:
- 将其加入到集合s中
- 用他来松弛其他的邻接点
- 松弛就是尝试刷新其邻接点的最短路
因为每次确定的将一个点加入集合n,每次加入后都尝试松弛,所以朴素dijk的时间复杂度是
O(N^2)
观察数据范围用二维数组存边
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e5 + 10;
int g[N][N], n, m;
int d[N];
bool v[N];
void dijk(int s)
{
memset(d, 0x3f, sizeof d);
d[s] = 0;
for (int i = 1; i <= n; i++)
{
// 这个-1是个小技巧,方便选择出集合外的点
int t = -1;
for (int j = 1; j <= n; j++)
if (!v[j] && (t == -1 || d[j] < d[t]))
t = j;
v[t] = true;
for (int j = 1; j <= n; j++)
if (d[j] > d[t] + g[t][j])
d[j] = d[t] + g[t][j];
}
}
int main()
{
memset(g, 0x3f, sizeof g);
cin >> n >> m;
while (m--)
{
int x, y, w;
cin >> x >> y >> w;
if (x == y)
continue;
g[x][y] = min(g[x][y], w);
}
dijk(1);
cout << (d[n] == d[0] ? -1 : d[n]) << endl;
return 0;
}