#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 0x3f3f3f3f
#define vexnum 10000
typedef struct n{
    int Adjmatrix[11111][11111];
}MG;
int flag[11111] = {0},n,m;
MG x;
int random_num()
{
    int ran;
    
    ran = rand() % 10000 + 1;
    
    return ran; 
}
void Dij(int t[],int lw[])
{
    int i,j,k,min;

    for(i = 1; i <= vexnum; i++){
        lw[i] = x.Adjmatrix[1][i];
        t[i] = 1;
    }

    t[0] = -1;
    flag[1]=1;

    for( i=2 ; i <= vexnum ; i++){
        min = MAX;

        for( j=1 ; j<=vexnum ; j++ ){
            
            if( !flag[j] && lw[j]<min ){
                min = lw[j];
                k = j;
            }
        }

        flag[k] = 1;

        for( j=2; j<=vexnum ; j++){

            if( !flag[j] && min+x.Adjmatrix[k][j] < lw[j] ){

                lw[j] = min + x.Adjmatrix[k][j];
                t[j] = k;
            }
        }
    }
}
int main()
{
    int i,j,sum=0;
    int path[11111],lowcost[11111];
    int u,v,w,pre;

    srand( (unsigned)time( NULL ) );
    //建立矩阵
    for(i=1;i<=vexnum;i++)
        for(j=1;j<=vexnum;j++){

            x.Adjmatrix[i][j] = MAX;
        }

    for(i = 1; i <= vexnum; i++){
        m = random_num();
        for(j = 1;j <= m; j++){
            v = random_num();
            w = random_num();
                    
            if(x.Adjmatrix[i][v] > w && i != v){
               x.Adjmatrix[i][v] = w;
           }
    }
    }

    Dij(path,lowcost);
    for(i = 2; i <= vexnum; i++){
        sum = sum + lowcost[i];
    }
    
    printf("%d\n",sum);

    freopen( "lowcost.txt", "w", stdout );
    for(i = 1; i <= vexnum; i++){
        printf("lowcost[%d] : %d\n",i,lowcost[i]);
    }
    freopen( "path.txt", "w", stdout );    
    for(i = 1; i <= vexnum; i++){
        pre = i;
        printf("v1--v%d : %d\n",pre,lowcost[i]);
        if(lowcost[i] == MAX){
            printf("v1 to v%d has no shortest path\n",i);
        }
        else{
             do{
                printf("v%d<--",pre);
                 pre = path[pre];
                }while(pre != 1);
        
                printf("v1\n");
            }
        }
    return 0;
}