朴素dijkstra算法

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;
}