CF

#include<stdio.h>
#include<iostream>
#include<cstdlib>

#define pf printf
#define sf scanf
#define pi 3.141592653589793116
#define INF 99999
#define maxInt 99999999
#define maxNEG -99999999.0
#define debug cout<<"Hello here!"<<endl;
#define readFile freopen("in.txt","r",stdin);

#define NULL_VALUE -999999
#define INFINITY 999999
#define MAX_HEAP_SIZE 100000
#define MAXREAL 999999.0


using namespace std;

/**
    Keeping track of edge and weight
*/
class edge{
public:
    int dest;
    float weight;

    edge(){
        dest=0;
        weight=0;
    }

    edge(int v,float w){
        dest=v;
        weight=w;
    }
};


//****************Dynamic ArrayList class based************************
class ArrayList
{
    edge * list;
    int length ;
    int listMaxSize ;
    int listInitSize ;
public:
    ArrayList() ;
    ~ArrayList() ;
    int searchItem(edge item) ;
    void insertItem(edge item) ;
    void removeItem(edge item) ;
    void removeItemAt(int item);
    edge getItem(int position) ;
    int getLength();
    void reset(){
        free(list);
        listInitSize=512;
        listMaxSize=listInitSize;
        length = 0 ;
    }

    bool empty();
    void printList();

    void reallocList(){
        listInitSize = 4 ;
        listMaxSize = listInitSize ;
        list = new edge[listMaxSize] ;
    }
} ;

//Initializing list
ArrayList::ArrayList()
{
    listInitSize = 512 ;
    listMaxSize = listInitSize ;
    list = new edge[listMaxSize] ;
    length = 0 ;
}

void ArrayList::insertItem(edge newEdge)
{
    edge * tempList ;
    if (length == listMaxSize)
    {
        //allocate new memory space for tempList
        listMaxSize = 2 * listMaxSize ;
        tempList = new edge[listMaxSize] ;
        int i;
        for( i = 0; i < length ; i++ )
        {
            tempList[i] = list[i] ; //copy all items from list to tempList
        }
        delete[] list ; //free the memory allocated before
        list = tempList ; //make list to point to new memory
    };

    list[length] = newEdge ; //store new item
    length++ ;
}

int ArrayList::searchItem(edge item)
{
    if(length==0) return NULL_VALUE;
    int i = 0;
    for (i = 0; i < length; i++)
    {
        if( list[i].dest == item.dest && list[i].weight == item.weight ) {
            return i;
        }
    }
    return NULL_VALUE;
}

void ArrayList::removeItemAt(int position) //do not preserve order of items
{
    if ( position < 0 || position >= length ) return ; //nothing to remove
    list[position] = list[length-1] ;
    length-- ;
}


void ArrayList::removeItem(edge item)
{
    int position;
    position = searchItem(item) ;
    if ( position == NULL_VALUE ) return ; //nothing to remove
    removeItemAt(position) ;
}


edge ArrayList::getItem(int position)
{
    if(position < 0 || position >= length) {
        //cout<< "No such edge found....\n";
        edge temp(0,0);
        return temp;
    }
    return list[position] ;
}

int ArrayList::getLength()
{
    return length ;
}

bool ArrayList::empty()
{
    if(length==0)return true;
    else return false;
}

void ArrayList::printList()
{
    int i;
    for(i=0;i<length;i++)
        printf("Vertex: %d, Edge: %d", list[i].dest,list[i].weight);
    printf("Current size: %d, current length: %d\n", listMaxSize, length);
}

ArrayList::~ArrayList()
{
    if(list) delete [] list;
    list = 0 ;
}

//******************ArrayList class ends here*************************

//******************Graph class starts here**************************
class Graph
{

    int nVertices, nEdges ;
    bool directed ;
    ArrayList  * adjList ;
    int **cost;
    int **w;
    //define other variables required for bfs such as color, parent, and dist
    //you must use pointers and dynamic allocation

public:
    int vtrack;
    Graph(bool dir=false);
    ~Graph();
    void setnVertices(int n);
    void addEdge(int u, int v,int w);
    void removeEdge(int u, int v,int w);
    void printGraph();

    void removeIT(int n){
        if(vtrack==1) return;
        for(int i=1;i<=nVertices;i++)
            adjList[i].removeItem(edge(n,cost[i][n]));
        adjList[n].reset();
        vtrack--;
    }

    void setnEdges(int n){
        //eLength=0;
        //nEdges=n;

        //e=new edgeExtra[n];
        cost=new int*[n + 1];
        for(int i=0;i<=n;i++) cost[i]=new int[n +1];
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)
            cost[i][j]=INFINITY;
    }


    void Floyad_warshall(){
        //Initializing
        long long int ans=0;

        for(int i=0;i<=nVertices;i++)
            for(int j=0;j<=nVertices;j++)
            {
                if(i==j) w[i][j]=0;
                else
                    w[i][j]=INF;
            }


        for(int i=1;i<=nVertices;i++){
            for(int j=0;j<adjList[i].getLength();j++){
                int des,wei;
                des=adjList[i].getItem(j).dest;
                wei=adjList[i].getItem(j).weight;
                if(des >nVertices or des<1) continue;
                w[i][des]=wei;
            }
        }

        for(int k=1;k<=nVertices;k++)
        {
            for(int i=1;i<=nVertices;i++)
            {
                for(int j=1;j<=nVertices;j++)
                {
                    if(w[i][k]==INF or w[k][j]==INF) continue;
                    if(w[i][j] > w[i][k] + w[k][j] )
                    {
                        w[i][j]=w[i][k] +w[k][j];

                    }
                }
            }
        }

        for(int i=1;i<=nVertices;i++){
            for(int j=1;j<=nVertices;j++){
                if(w[i][j]==INF) continue;
                else ans+=w[i][j];
            }

        }

        cout<<ans<<endl;

    }

};


Graph::Graph(bool dir)
{
    //Initializing the graph
    w=0;
    cost=0;
    nVertices = 0 ;
    nEdges = 0 ;
    adjList = 0 ;
    directed =dir;
    vtrack=0;

}

void Graph::setnVertices(int n)
{
    this->nVertices = n ;
    vtrack=n;

    if(adjList!=0) delete[] adjList ; //delete previous list
    //delete previous record

    adjList = new ArrayList[nVertices+1] ;
    w=new int*[nVertices +1];
    for(int i=0;i<=nVertices;i++) {
        w[i]=new int[nVertices + 1];
    }

    //cout<< "Initializing vertices at 1\n" ;
}

void Graph::addEdge(int u, int v,int w)
{
    if(u<=0 || v<=0 || u>nVertices || v>nVertices) {
        //cout<< "Vertices out of range\n";
        return;
    } //vertex out of range
    //this->nEdges++ ;
    adjList[u].insertItem(edge(v,w)) ;
    cost[u][v]=w;

    //if(!directed) adjList[v].insertItem(edge(u,w)) ;
}

void Graph::removeEdge(int u, int v,int w)
{
    if(u<1 || u>nVertices || v<1 || v>nVertices){
        //cout<< "Out of bound...\n";
        return;
    }
    //write this function
    adjList->removeItem(edge(u,w));
    adjList->removeItem(edge(v,w));
}


void Graph::printGraph()
{
    printf("\nNumber of vertices: %d, Number of edges: %d\n", nVertices, nEdges);
    for(int i=0;i<nVertices;i++)
    {
        printf("%d:", i);
        for(int j=0; j<adjList[i].getLength();j++)
        {
            printf(" Vertex: %d, Edge: %d", adjList[i].getItem(j).dest,adjList[i].getItem(j).weight);
        }
        printf("\n");
    }
}


Graph::~Graph()
{
    if(adjList!=0) delete[] adjList ; //delete previous list
}

int edgeCount(int n){
    //nCr
    return (n*(n-1));
}

int main(){

    //freopen("test.txt", "r",stdin);

    int n,m,x;
    int u,v,w;

    Graph g;

    scanf("%d",&n);
    if(n==1) m=1;
    else m=edgeCount(n);
    //cout<< "m: "<<m<<endl;

    g.setnVertices(n);
    g.setnEdges(m);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            sf("%d",&x);
            if(i==j) continue;
            else{
                g.addEdge(i,j,x);
            }
        }
    }

    for(int i=0;i<n;i++)
    {
        g.Floyad_warshall();
        sf("%d",&x);
        if(g.vtrack==1) break;
        cout<< "Vtrack: "<<g.vtrack<<endl;
        g.removeIT(x);
    }

    return 0;

}

/**
*/