//Prepare the distance matrix in file ff.dat
//s is the membership array for the solution set
//f is that for the frontier set
#include <stdio.h>
main(){
int i,j,k,n,v,w;
int d[1000],f[1000],s[1000];
int a[100][100];
FILE *in_file;
//  printf("Input n ");
//  scanf("%d",&n);
  in_file=fopen("ff.dat","r"); 
  fscanf(in_file,"%d",&n);
  fscanf(in_file, "\n");
  for (i=1;i<=n;i++) {
    for (j=1;j<=n;j++) fscanf(in_file, "%d ",&a[i][j]);
    fscanf(in_file, "\n");
  };
  for (i=1;i<=n;i++){
    for (j=1;j<=n;j++) printf("%4d ",a[i][j]);
    printf("\n");
  }
  for (j=1;j<=n;j++){
    d[j]=a[1][j]; s[j]=0;
    f[j]=0;
  }; 
  f[1]=1;
  getchar();
  d[0]=99;  
  for (j=1;j<=n;j++){ 
    v=0; 
    for (w=1;w<=n;w++) 
      if (f[w]==1) if (d[w]<d[v]) v=w;
    s[v]=1; f[v]=0;
    printf("%d selected\n",v);
    for (w=1;w<=n;w++)  if (a[v][w]<99) 
      if (s[w]==0){ 
		  if (f[w]==1){   
          if (d[v]+a[v][w]<d[w])  
			  d[w]=d[v]+a[v][w];}
        else { 
          d[w]=d[v]+a[v][w];
          f[w]=1;
        }
      }
      printf("vetices      ");
      for (w=1;w<=n;w++) printf("%d  ",w); printf("\n");
      printf("frontier     ");
      for (w=1;w<=n;w++) printf("%d  ",f[w]); printf("\n");
      printf("solution set ");
	  for (w=1;w<=n;w++)printf("%d  ",s[w]); printf("\n");
	  printf("    d=     ");
      for (w=1;w<=n;w++) printf("%3d", d[w]); getchar();
      printf("\n");
  };
}