Cod sursa(job #1624151)

Utilizator catalin15Bahrin Catalin catalin15 Data 2 martie 2016 08:32:22
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <queue>
#define inf 10000000
using namespace std;

ifstream fin ( "ubuntzei.in" ) ;
ofstream fout ( "ubuntzei.out" ) ;

int n , node_start , cost[2002][2002] , vis[2002]  , dist[2002]  , father[2002], C[2002], k, suma;

void set_cost() {
    for ( int i = 1 ; i <= n ; i++ )
        for ( int j = i + 1 ; j <= n ; j++ )
            cost[i][j] = cost[j][i] = inf ;
}

void prepare() {
    for ( int i = 1 ; i <= n ; i++ ) {
        dist[i] = cost[node_start][i] ;
        father[i] = node_start ;
    }
    vis[node_start] = 1 ;
    father[node_start] = 0 ;
}

void read() {
    fin >> n >> node_start ;
    node_start=1;
    set_cost() ;
    fin>>k;
    for(int i=1; i<=k; i++)
        fin>>C[i];
    while ( !fin.eof() ) {
        int x , y , z ;
        fin >> x >> y >> z ;
        cost[x][y] = z ;
        cost[y][x]=z;
    }
    prepare() ;
}

void solve() {
    int dmin , vfmin ;
    for ( int j = 1 ; j <= n ; j++ ) {
        dmin = inf ;
        for ( int i = 1 ; i <= n ; i++ )
            if ( !vis[i] && dmin > dist[i] ) {
                dmin = dist[i] ;
                vfmin = i ;
            }
        vis[vfmin] = 1 ;
        for ( int i = 1 ; i <= n ; i++ )
            if ( !vis[i] && dist[i] > dmin + cost[vfmin][i] ) {
                father[i] = vfmin ;
                dist[i] = dmin + cost[vfmin][i] ;
            }
    }
}

void print() {
    for ( int i = 1 ; i <= n ; i++ )
        if ( dist[i] == inf )
            fout << "-1" << ' ' ;
        else
            fout << dist[i] << ' ' ;
}
int main() {
    read() ;
    solve() ;
    for(int i=1; i<=k; i++) {
        suma+=dist[C[i]];
    }
    suma+=dist[n];
    fout<<suma;

    return 0;
}