输入 输入的第一行包含2个正整数n和s，表示图中共有n个顶点，且源点为s。其中n不超过50，s小于n。 以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。 输出 只有一行，共有n-1个整数，表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。 请注意行尾输出换行。 输入样例 1 4 1 0 3 0 1 0 0 4 0 2 0 0 0 0 0 1 0 输出样例 1 6 4 7 用c++写出来

#include <iostream>
#include <cstring>
using namespace std;

const int N = 55, INF = 0x3f3f3f3f;
int n, s, g[N][N], dis[N];
bool st[N];

int dijkstra()
{
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        if (t == -1) break;
        st[t] = true;
        for (int j = 1; j <= n; j ++ )
            dis[j] = min(dis[j], dis[t] + g[t][j]);
    }
    if (dis[n] == INF) return -1;
    return dis[n];
}

int main()
{
    cin >> n >> s;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> g[i][j];
    cout << dijkstra() << endl;
    return 0;
}