Dijskra（迪杰斯特拉）最短路径算法

#include<bits/stdc++.h>

using namespace std;

int n, s, dis[55], scan[55], node[55][55], num, cur, inf = 1e5;

int findNext(){

    int loc = -1, minDis = -1;

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

        if(scan[i]) continue;

        if(minDis == -1) minDis = dis[i], loc = i;

        else {

                if(minDis > dis[i]) minDis = dis[i], loc = i;

        }

    }return loc;

}

int main() {

    for(int i = 0; i < 55; i++) dis[i] = inf;

    cin >> n >> s;

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

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

                cin >> num;

                node[i][j] = num;

        }dis[s] = 0;

    for(int cnt = 1; cnt < n; cnt++){ 

        if((cur = findNext()) == -1) break;

        scan[cur] = 1;

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

             if(node[cur][i] == 0) continue;

            dis[i] = min(dis[i], node[cur][i] + dis[cur]);

        }

    }

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

        if(i == s) continue;

        if(dis[i] == inf) cout << -1 << ' ';

        else cout << dis[i] << ' ';

    }cout << "\n";

    return 0;

}