Dijkstra

#include <stdio.h>
#define MAXN 100
#define inf 1000.0

double dist[MAXN];
int p[MAXN];
void dijk(int u, double C[MAXN][MAXN], int n){
    bool s[MAXN] = {false};

    for(int i = 0; i < n; i++){
        dist[i] = C[u][i];
        if(dist[i] >= inf)  p[i] = -1;
        else  p[i] = u;
    }

    dist[u] = 0;
    s[u] = true;

    for(int i = 0; i < n; i++){
        double tmp = inf;
        int t = u;
        for(int j = 0; j < n; j++)
        if(!(s[j]) && (dist[j] < tmp)){
            t = j;
            tmp = dist[j];
        }

        if(t == u)  break;
        s[t] = true;

        for(int j = 0; j < n; j++)
        if(!(s[j]) && (C[t][j] < inf) && (dist[j] > dist[t] + C[t][j])){
            dist[j] = dist[t] + C[t][j];
            p[j] = t;
        }
    }
}

int main(){
    double C[MAXN][MAXN];
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            scanf("%lf", C[i]+j);

    dijk(0, C, n);

    for(int i = 0; i < n; i++)
        printf("%.4f\t", dist[i]);
    printf("\n");
    for(int i = 0; i < n; i++)
        printf("%d\t", p[i]);

    return 0;
}