Pagini recente » Cod sursa (job #2250939) | Cod sursa (job #1389268) | Cod sursa (job #1641193) | Cod sursa (job #1832153) | Cod sursa (job #1624151)
#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;
}