#include "d:\scilab-4.0\routines\stack-c.h"
void eff __PARAMS((int *a, int m, int n, double *b));

int inteff(fname) 
char *fname;
{
    static int l1, m1, n1, l2,m2;
    static int minlhs=0, maxlhs=1, minrhs=1, maxrhs=1;   //why the minlhs must equal zero??
    static int tmp1,tmp2,tmp3;
    static int m3,n3,m4,n4;

    CheckRhs(minrhs,maxrhs) ;
    CheckLhs(minlhs,maxlhs) ;

    GetRhsVar(1, "i", &m1, &n1, &l1);   //the following sentence must be wrote together!!!! 
    m2=1;
    CreateVar(2, "d", &m2, &m2, &l2);  
    eff(istk(l1), m1, n1, stk(l2));
    /*  Return C (3)  */
    LhsVar(1) = 2;
    return 0;
}


/*
  Name:  Calculate the shortest path
  Copyright: GPL
  Author:  wUBo
  Date: 07-08-06 13:28
  Description: Calucate the shortest algorithm 
*/
#include <stdio.h>


#define inf 9999
#define null -1


int N;
//int g[N][2000];  //N是出发节点，邻居数，后面依次为邻居的索引 
//int D[N];   //Distance  
//int P[N];   //Record the path 
int **g;
int *D;
int *P;
double aver_dis;


void init(int s)
{
    int i; 
    for (i=0;i<N;i++) {
        D[i]=inf;
        P[i]=null;
    }
    D[s]=0;

}

void relax(int u, int v)
{
    if (D[v]>D[u]+1) {
        D[v]=D[u]+1;
        P[v]=u;
    }
}

int bellman_ford(int s)
{

    int i,j,k;
    init(s);
    for (i=0;i<N-1;i++) {
        for (j=0;j<N;j++)
            for (k=1;k<=g[j][0];k++)
                relax(j,g[j][k]);
    }       
    for (j=0;j<N;j++)
        for (k=1;k<=g[j][0];k++)
            if (D[j]>D[g[j][k]]+1)
                return -1;



            else {
                for (j=0;j<N;j++)
                    if (D[j]!=0&&D[j]!=9999)
                        aver_dis+=1.0/D[j];
//			   sciprint("%e\n",aver_dis);
                return 1;
            }

}



//eff __PARAMS((int *a, int m, int n, double *b));

void eff(a,m,n,b)
int a[];
int m,n;
double b[];
{
    int i,j;
    N=m;
    D=(int *) malloc(N * sizeof(int));
    P=(int *) malloc(N * sizeof(int));
    aver_dis=0;

    /////////////////////////////////////////////////
    g=malloc(N*sizeof(int *));
    for (i=0;i<N;i++)
        g[i]=malloc(2000*sizeof(int));   //generate g[N][600]
    ////////////////////////////////////////////////////

    for (i=0;i<N;i++) {
        for (j=0;j<=a[i];j++) {
            g[i][j]=a[i+j*N];
//			sciprint("%i ",g[i][j]);

        }
//		 sciprint("\n");

    }  


    for (j=0;j<N;j++) {
        if (j%10==0)
            sciprint("%i\t",j);
        if (j%100==0)
            sciprint("\n");
        init(j);
        bellman_ford(j); 

    }
    b[0]=aver_dis/(N*(N-1));
//	sciprint("%e\n",1.0/aver_dis*(N*(N-1)));
    free(g);
    free(D);
    free(P);

}



