1075.安全网络 ver.2

#include <cstdio>
#include <cstdlib>
#include <iostream>
#define inf 0x3fffffff
using namespace std;

bool b[101];
int a[101][101];
int d[101];
int n;

int dijkstra() {
    int i, j, s, t;

    for (i = 1; i <= n; i++) {
        d[i] = a[1][i];
        b[i] = false;
    }
    b[1] = true;

    for (i = 2; i <= n; i++) {
        t = 1;
        s = inf;
        for (j = 2; j <= n; j++) {
            if (b[j] || d[j] > s)
                continue;
            t = j;
            s = d[j];
        }
        if (t == n)
            return s;
        b[t] = true;
        for (j = 2; j <= n; j++)
            if (!b[j] && d[j] > d[t] + a[t][j])
                d[j] = d[t] + a[t][j];
    }
    return -1;
}

int main(int argc, char* argv[]) {
    int i, j;

    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);

    printf("%d\n", dijkstra());

    return 0;
}