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