algo2017_week9_AStar

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define fo(n) for(int i=0;i<n;i++)
#define fos(o,n) for(int i=o;i<=n;i++)
#define MAX 11

int w[MAX][MAX] , d[MAX];
bool vis[MAX];

void dijkstra( int s ){
    fo( MAX ) vis[i] = 0 , d[i] = INF;

    d[s] = 0;

    fo( MAX ){

        int a = -1 , min = INF;

        for( int j = 0 ; j < MAX ; ++j )
            if( !vis[j] && d[j] < min ) a = j , min = d[j];

        if( a == -1 ) break;
        vis[a] = 1;

        for( int j = 0 ; j < MAX ; ++j )
            if( !vis[j] && d[a] + w[a][j] < d[j] ) d[j] = d[a] + w[a][j];

    }
}


int main(){

    fo( MAX )
        for( int j = 0 ; j < MAX ; ++j )
            w[i][j] = INF;

    cin >> w[0][1] >> w[0][2] >> w[0][3];

    for( int i = 1 ; i < 5 ; i += 3 ){
        for( int j = i ; j < i + 3 ; ++j )
            for( int k = i + 3 ; k < i + 6 ; ++k )
                cin >> w[j][k];
    }

    cin >> w[7][10] >> w[8][10] >> w[9][10];

    dijkstra( 0 );

    int s , ans = 1e7;

    cin >> s;

    for( int i = 1 + 3 * ( s - 2 ) ; i < 1 + 3 * ( s - 2 ) + 3 ; ++i ){
        int mi = 1e7;
        for( int j = 0 ; j < MAX ; ++j ) mi = min( mi , w[i][j] );
        ans = min( ans , d[i] + mi );
    }

    cout << ans << endl;

    return 0;
}