邻接矩阵求最短路，代码简单，建议学懂原理之后来看这个代码，非常清晰

解题思路:

注意事项:堆优化更好，不过本题不使用对优化的原因是本题直接给邻接矩阵，方便

参考代码:

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

const int N = 510, inf = 1e9 + 10;

int n, s;

int g[N][N], dist[N];

bool st[N];

void dijkstra()

{

    memset(dist, 0x3f, sizeof dist);

    dist[s] = 0;

    for (int i = 0; i < n; i++)

    {

        int t = -1;

        for (int j = 0; j <n; j++)

            if (!st[j] && (t == -1 || dist[t] > dist[j]))

                t = j;

        st[t] = true;

        for (int j = 0; j <n; j++)

            dist[j] = min(dist[j], dist[t] + g[t][j]);

    }

}

int main()

{

    cin >> n >> s;

    memset(g, 0x3f, sizeof g);

    for (int i =0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            cin >> g[i][j];

            if (g[i][j] == 0 && i != j)

                g[i][j] = inf;

        }

    }

    dijkstra();

    for (int i = 0; i <n; i++)

    {

        if (i != s)

        {

            if (dist[i] >inf/2)

                cout << "-1 ";

            else

                cout << dist[i] << " ";

        }

    }

    puts("");

    return 0;

}